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;
}