[백준 2644] 촌수계산 - Python(그래프 탐색, BFS)

 

2644번: 촌수계산

 

<내 코드>

 

from collections import deque


def bfs(s):
    q = deque()
    visited = [0 for _ in range(n+1)]

    q.append(s)
    visited[s] = 1

    while q:
        x = q.popleft()

        for i in tree[x]:
            if visited[i] == 0:
                visited[i] = 1
                result[i] = result[x] + 1
                q.append(i)


n = int(input())
a, b = map(int, input().split())
m = int(input())
tree = [[] for _ in range(n+1)]
result = [0 for _ in range(n+1)]

for _ in range(m):
    x, y = map(int, input().split())
    tree[x].append(y)
    tree[y].append(x)

bfs(a)
if result[b] != 0:
    print(result[b])
else:
    print(-1)

BFS로 그래프를 탐색하며 현재 탐색하는 노드와 연결된 노드에 현재 노드 값의 +1을 한다. 즉, 연결된 노드를 이동하는 것을 의미한다.

이런 식으로 모든 노드들을 탐색을 마치면 찾고자 하는 노드의 인덱스의 값을 출력해주면 된다.