[백준-2644] 촌수계산

문제

링크

코드

from collections import deque
n = int(input())
a, b = map(int, input().split())

m = int(input())

fam = [[] for _ in range(n+1)]
visited = [0] * (n+1)
for _ in range(m) :
    x, y = map(int, input().split())
    fam[x].append(y)
    fam[y].append(x)
    
queue = deque()
queue.append(a)
while queue : 
    q = queue.popleft()
    for f in fam[q] :
        if visited[f] == 0 :
            queue.append(f)
            visited[f] = visited[q] + 1
            if f == b :
                break

if visited[b] == 0 :
    print(-1)
else :
    print(visited[b])

풀이

너비 우선 탐색(BFS)로 문제를 풀었다.

1. 촌수를 계산해야 하는 서로 다른 두 사람 중 한 명의 번호를 큐에 넣는다.
2. while문 내에서 popleft해서 맨 앞 번호를 꺼낸다. 이때 while은 큐가 빌 때까지 돌아간다.
3. 해당 번호와 연결된 번호들 중 방문한 적 없는 번호를 모두 큐에 넣는다. 이때 연결된 방문 번호는 해당 번호의 방문 값 + 1을 한다.
   3-1. 이때 촌수를 계산해야 하는 다른 번호이면 반복문을 멈춘다
   3-2. 아니면 2번으로 돌아간다.
4. 해당 번호의 방문 번호가 0보다 크면 출력하고, 0이면 친척 관계가 전혀 없다는 뜻이므로 -1을 출력한다.