BOJ 2644 · 촌수계산

알고리즘 분류 : BFS  

BFS를 통해 촌수를 계산하는 문제다.

• 촌수는 거리로 바꿔서 생각하면 된다.
• 부모와 자식 간의 관계를 인접리스트로 변환하여 저장한다.
• 사람(X) 부터 BFS로 탐색하면서 사람(Y)를 만나면 종료한다.
• BFS 탐색이 끝날 때 까지 사람(Y)를 만나지 못하면, 촌수 계산이 불가능하므로 -1을 출력한다.

---

C++ 소스코드

#include <cstdio>
#include <queue>
#include <vector>
using namespace std;

int n;
int x, y;
vector<int> a[101];
int dist[101];

int bfs() {
    queue<int> q;
    q.push(x);
    while (!q.empty()) {
        int now = q.front();
        q.pop();
        if (now == y) return dist[now];
        for (int i=0; i<(int)a[now].size(); i++) {
            int next = a[now][i];
            if (dist[next]) continue;
            q.push(next);
            dist[next] = dist[now] + 1;
        }
    }
    return -1;
}

int main() {
    scanf("%d", &n);
    scanf("%d %d", &x, &y);
    int m;
    scanf("%d", &m);
    for (int i=0; i<m; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        a[u].push_back(v);
        a[v].push_back(u);
    }
    printf("%d\n", bfs());
    return 0;
}

---

Python 3 소스코드

from collections import deque
from sys import stdin
input = stdin.readline

n = int(input())
x, y = map(int, input().split())
a = [[] for _ in range(n+1)]
dist = [0 for _ in range(n+1)]
for _ in range(int(input())):
    u, v = map(int, input().split())
    a[u].append(v)
    a[v].append(u)

def bfs():
    q = deque()
    q.append(x)
    while q:
        now = q.popleft()
        if now == y:
            return dist[now]
        for i in a[now]:
            if dist[i] == 0:
                q.append(i)
                dist[i] = dist[now] + 1
    return -1

print(bfs())

---

참고

• 백준 온라인 저지 : BOJ 2644