[BOJ] 2644 : 촌수계산 - 파이썬(Python)

문제 해석

---

 

두 사람의 촌수를 구한다는 의미는 입력받은 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 탐색 시작 노드와 탐색 종료 노드를 뜻하는 것이라고 볼 수 있다.

 

 

문제 풀이

---

import sys
from collections import deque


N = int(sys.stdin.readline().rstrip())

x, y = map(int, sys.stdin.readline().split())

M = int(sys.stdin.readline().rstrip())

graph = [[] for _ in range(N + 1)]

visited = [0 for _ in range(N + 1)]

for _ in range(M):
    v1, v2 = map(int, sys.stdin.readline().split())
    graph[v1].append(v2)
    graph[v2].append(v1)


deq = deque()

deq.append(x)
cnt = 0
while deq:
    a = deq.popleft()
    for b in graph[a]:
        if visited[b] == 0:
            visited[b] = visited[a] + 1
            deq.append(b)

if visited[y] > 0:
    print(visited[y])
else:
    print(-1)

 

 

BFS를 이용해서 풀기 위해 입력 받은 가족 관계를 바탕으로 그래프를 만든다.

 

그리고 방문처리를 할 때 0으로 초기화된 방문처리를 위한 리스트 visited의 값을 인접 노드를 방문할때마다 1씩 증가시킨다.

 

그렇게 하면 시작 노드부터 종료 노드까지 몇번의 방문을 진행했는지를 알 수 있고 그 방문을 진행한 횟수가 문제에서 말하는 촌수이다.