[C++] 백준 2644번 촌수계산

https://www.acmicpc.net/problem/2644

풀이

두 사람 간의 최단 거리를 구해야 하므로 BFS를 이용했다.
기존에 단순히 탐색하는 노드 번호만 큐에 넣었던 것과는 달리, 깊이(d)도 저장할 수 있도록 (노드, 깊이) 쌍을 큐에 넣었다.

코드

#include <iostream>
#include <queue>
using namespace std;

int main()
{
    int n, m, a, b, x, y;
    int ans = -1;
    bool graph[101][101] = {};
    bool visited[101] = {};
    queue<pair<int, int>> q;
    
    cin >> n >> a >> b >> m;
    
    while(m--) {
        cin >> x >> y;
        graph[x][y] = graph[y][x] = true;
    }
    
    q.push({a, 0});
    visited[a] = true;
    
    while(!q.empty()) {
        int p = q.front().first;
        int d = q.front().second;
        q.pop();
        
        if(p == b) {
            ans = d;
            break;
        }
        
        for(int i=1; i<=n; i++) {
            if(graph[p][i] && !visited[i]) {
                visited[i] = true;
                q.push({i, d+1});
            }
        }
    }
    
    cout << ans;
    return 0;
}