[Algorithm] [백준] 2644 - 촌수계산 (BFS)

## 백준 2644 촌수계산
# BFS

import sys
from collections import deque
input = sys.stdin.readline

def BFS(start):
    queue = deque()
    queue.append(start)
    visited[start] = 1
    while queue:
        d = queue.popleft()
        for i in graph[d]:
            if visited[i] == 0:
                visited[i] = 1
                result[i] = result[d] + 1
                queue.append(i)


n = int(input())  # 사람 수
a, b = map(int, input().split())  # a와 b의 촌수
m = int(input())  # 부모와 자식들 간의 관계의 개수

graph = {}
for i in range(n):
    graph[i+1] = set()

for j in range(m):
    c, d = map(int, input().split())
    graph[c].add(d)
    graph[d].add(c)

visited = [0] * (n+1)
result = [0] * (n+1)
BFS(a)

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

start를 기준으로, 노드를 하나씩 거쳐갈수록 촌수가 1씩 늘어난다. 따라서 촌수를 나타내는 리스트 result를 만들고, result[i] = result[d] + 1 를 통해 d의 촌수에 1씩 더한다.

BFS를 사용하여 deque를 이용하였다.

그냥 리스트를 이용해도 된다.
아래 코드에서는 queue 라는 변수를 사용하였다.

import sys
#from collections import deque
input = sys.stdin.readline

def BFS(start):
    queue = []
    queue.append(start)
    visited[start] = 1
    while queue:
        d = queue.pop()
        for i in graph[d]:
            if visited[i] == 0:
                visited[i] = 1
                result[i] = result[d] + 1
                queue.append(i)


n = int(input())  # 사람 수
a, b = map(int, input().split())  # a와 b의 촌수
m = int(input())  # 부모와 자식들 간의 관계의 개수

graph = {}
for i in range(n):
    graph[i+1] = set()

for j in range(m):
    c, d = map(int, input().split())
    graph[c].add(d)
    graph[d].add(c)


visited = [0] * (n+1)
result = [0] * (n+1)
BFS(a)

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