BFS 문제 분석-2(촌수계산)

1. 촌수계산 문제 분석(boj.kr/2644)

이 문제도 사실 미로찾기 문제와 다를게 없다. 방문체크를 노드기준으로 한다는 것과 다르게.

입력된 상태를 노드로 표현하면 다음과 같다.

이제 BFS를 해야한다. 시작하는 위치는 두 사람의 어느곳이든 상관없다. 

나는 7에서 시작한다고 가정하겠다.

그렇다면, BFS(7)로 탐색이 시작된다.

미로탐색에서 쓰였던 방법처럼, 현재 노드까지의 최단경로에서 +1을 다음노드에 해준다. 

7과 연결된 노드는 2와 8이다. 결과적으로 1+1이 된다. 7과 연결된 노드가 모두 방문되면, 다음 노드(q.front())를 꺼내서 연결된 노드를 방문한다. 2와 연결된 노드는 1, 7, 8, 9이다. 하지만 7은 방문되었으므로, 생각치 않는다. 1, 8 ,9의 방문체크를 2+1로 해준다. 다음 노드 1은 3+1로 해준다.

그런데, 4, 5, 6은 연결되지 않았으므로, visited는 0이다.

결과는 visited[from]-visited[to]를 하면 된다. 

코드

#include <cstdio>
#include <queue>
using namespace std;
 
#define MAX_SIZE 102
 
int N, p1, p2;
int edge[MAX_SIZE][MAX_SIZE];
int visited[MAX_SIZE];
int chonsu;
int edgeNum;
 
void bfs(int p1) {
    queue<int> q;
    q.push(p1);
 
    visited[p1] = 1;
 
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
 
        for (int i = 1; i <= N; ++i) {
            if (!visited[i] && edge[cur][i]) {
                visited[i] = visited[cur] + 1;
                
                if (visited[p2]) return;
 
                q.push(i);
            }
        }
    }
}
 
int main(void) {
 
    scanf("%d", &N);
    scanf("%d %d", &p1, &p2);
    scanf("%d", &edgeNum);
 
    for (int i = 0; i < edgeNum; ++i) {
        int a, b;
        scanf("%d %d", &a, &b);
        edge[a][b] = edge[b][a] = 1;
    }
    
    bfs(p1);
 
    if (visited[p2] == false) printf("%d\n", -1);
    else printf("%d\n", visited[p2]-visited[p1]);
 
    return 0;
}