BOJ 2644 촌수계산

1. BOJ 2644 촌수계산 

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

코드 

from collections import deque
import sys
input = sys.stdin.readline
 
N = int(input())
start, end = map(int, input().split())
m = int(input())
tree = [[] for _ in range(N+1)]
 
for i in range(m):
    x, y = map(int, input().split())
    tree[y].append(x)
    tree[x].append(y)
 
visited = [False]*(N+1)
cnt = [0]*(N+1)
 
queue = deque([start])
while queue:
    v = queue.popleft()
    visited[v] = True
    for i in tree[v]:
        if not visited[i]:
            queue.append(i)
            cnt[i] += cnt[v]+1
            visited[i] = True
 
if cnt[end]!=0:
    print(cnt[end])
else:
    print(-1)

설명

해당 문제는 BFS로 해결하였다. BFS는 1-hop으로 연결된 노드가 한번에 큐로 들어온다. 

촌수 계산은 이 'hop'수를 더하면 풀 수 있었다. 따라서 몇번째 hop인지 카운트해주는 cnt array를 하나 둔다. 
unvisited인 노드를 큐에 더한 후에 각 노드의 cnt[i]를 parent 노드(이번에 pop된 노드)의 cnt[v]에 1을 더한다. 

최종적으로, start에서부터 BFS를 진행했을 때, cnt[end]에는 start에서 몇 hop 떨어져있는지가 저장될 것이다. 
만약 0이라면 다른 component라는 뜻일 것이다.