[백준] 14496 : 그대, 그머가 되어

www.acmicpc.net/problem/14496

14496번: 그대, 그머가 되어

---

• 문제 설명은 굉장히 현란하지만, 결국 잘 읽어보면 최단거리를 구하는 문제이다.
• 그래프에서 에지의 가중치가 없고 전부 1이기 때문에, 단순한 BFS 문제로 생각하고 풀면 바로 풀 수 있다.
• 문제에서 노드들이 양방향으로 연결된다는 말은 없었는데, 예제 2번을 통해 유추하면 될 것 같다.

---

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int a, b, N, M, cnt;
int u, v;

int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> a >> b >> N >> M;

    vector<int> graph[N + 1];           // 엣지 리스트
    vector<bool> visited(N + 1, false); // 중복 방문 피하기 위한 배열

    for(int i = 0 ; i < M ; i++)
    {
        cin >> u >> v;
        graph[u].push_back(v);          // 양방향으로 연결
        graph[v].push_back(u);
    }

    queue<int> q;
    q.push(a);                          // 주어진 a 부터 시작해서
    visited[a] = true;

    while(q.size())
    {
        int sz = q.size();
        for(int k = 0 ; k < sz ; k++)   // 같은 너비에 있는 친구는 한번에 다같이 처리
        {
            int cur = q.front();
            q.pop();
            if(cur == b)
            {
                cout << cnt << endl;
                return 0;
            }
            for(int i = 0 ; i < graph[cur].size() ; i++)    // 자신에게 연결된 노드들 중
            {
                int next = graph[cur][i];
                if(!visited[next])                          // 방문하지 않은 노드에 대해서 푸시해주고
                {
                    q.push(next);
                    visited[next] = true;                   // 방문처리를 미리 해줌
                }
            }
        }
        cnt++;
    }

    cout << -1 << endl;
}