Algorithm-BOJ-2644

13 Mar 2019

Reading time ~1 minute

BOJ-2644-촌수계산

전형적인 BFS 문제, BFS그 자체이다. 주어진 두 사람간의 거쳐간 노드의 길이를 체크하면 된다.

dist를 촌수라고 할 때, 현재 q의 front노드가 방문한 곳이 아니라면 현재 촌수에서 +1시켜주면 된다.

while(!q.empty()) {
    int curr = q.front(); q.pop();
    if(curr == b) return dist[curr];
    
    for(int next : p[curr]) {
        if(dist[next]) continue;  // next가 0이 아니면 이미 방문한 곳, 패스
        q.push(next);
        dist[next] = dist[curr] + 1;
    }
}

풀이보기

```c++
    #include<iostream>
    #include<vector>
    #include<queue>
    using namespace std;
    
    vector<vector <int>> p;
    vector<int> dist;
    int n, a, b, m;
    
    int bfs() {
        queue<int> q;
        q.push(a);
        
        while(!q.empty()) {
            int curr = q.front(); q.pop();
            if(curr == b) return dist[curr];
            
            for(int next : p[curr]) {
                if(dist[next]) continue;  // next가 0이 아니면 이미 방문한 곳, 패스
                q.push(next);
                dist[next] = dist[curr] + 1;
            }
        }
        return -1;
    }
    
    int main(void) {
        scanf("%d", &n);
        scanf("%d %d", &a, &b);
        scanf("%d", &m);
        
        p.resize(n+1);
        dist.resize(n+1);
        while(m--) {
            int x, y;
            scanf("%d %d", &x, &y);
            // 밑에서 위로 찾아갈 수도 있어야 하니깐 양방향
            p[x].push_back(y);
            p[y].push_back(x);
        }
        
        printf("%d\n", bfs());
        
        return 0;
    }
```

c++Algorithm