[탐색/BFS] 백준 2644 촌수계산 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

2644번: 촌수계산

 

 

 

2. 문제 풀이

 촌수를 계산하는 문제입니다.

 

2022.02.23 - [Algorithm] - [Algorithm] 너비 우선 탐색(BFS), 가까운 주변부터 찾자

[Algorithm] 너비 우선 탐색(BFS), 가까운 주변부터 찾자

 가족관계도를 입력받고, 촌수를 계산해야 합니다. 가족도 '부모 - 자식' 간의 관계로, 그래프의 부모 노드 - 자식 노드와 똑같습니다. 부모관계를 입력받아 가족관계 그래프를 저장하고, BFS탐색 또는 DFS탐색으로 촌수를 계산합니다.

 

 

 

3. 코드

from collections import deque

# 입력
n = int(input())
start, end = map(int, input().split())
m = int(input())

graph = [[] for _ in range(n+1)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

# bfs 탐색
visited = [False] * (n+1)
queue = deque([(start, 0)])
visited[start] = True

while queue:
    x, cnt = queue.popleft()
    if x == end:
        print(cnt)
        break

    for i in graph[x]:
        if not visited[i]:
            queue.append((i, cnt+1))
            visited[i] = True
else:
    print(-1)

 BFS 코드에 대한 설명은 위 링크에서 찾아보실 수 있습니다.