백준 | 촌수계산

백준 촌수계산

가족 관계를 그래프(노드: 사람, 간선: 관계)로 표현할 수 있고, 촌수는 두 노드 간 최단 경로이므로 BFS로 접근했다.

import sys
from collections import deque

n = int(sys.stdin.readline().strip())
start_p, target_p = map(int, sys.stdin.readline().strip().split())
m = int(sys.stdin.readline().strip())

# graph: 가족 및 친척들 사이의 관계
graph = [[] for _ in range(n + 1)]
for _ in range(m):
    x, y = map(int, sys.stdin.readline().strip().split())

    graph[x].append(y)
    graph[y].append(x)

# BFS를 이용해 주어진 두 사람의 촌수를 계산한다.
def bfs(start, target):
    # queue에는 (현재 탐색 중인 사람 번호, 촌수)를 저장한다.
    queue = deque([(start, 0)])

    visited = [False] * (n + 1)
    visited[start] = True

    while queue:
        current, degree = queue.popleft()

        if current == target:
            return degree

        for neighbor in graph[current]:
            if not visited[neighbor]:
                visited[neighbor] = True
                queue.append((neighbor, degree + 1))
    
    return -1

result = bfs(start_p, target_p)
print(result)