백준 - 촌수계산 / Silver 2 / 2644번 / Python

문제 📋

백준 - 촌수계산

풀이 📝

import sys
from collections import defaultdict, deque


def solution(graph, n, start, target):
    breadth = 0
    visited = [False] * (n + 1)

    q = deque([start])
    visited[start] = True

    while q:
        for _ in range(len(q)):
            node = q.popleft()

            if node == target:
                return breadth

            for next_node in graph[node]:
                if not visited[next_node]:
                    q.append(next_node)
                    visited[next_node] = True
        breadth += 1
    return -1


n = int(sys.stdin.readline())
start, target = map(int, sys.stdin.readline().split())
m = int(sys.stdin.readline())

graph = defaultdict(list)

for _ in range(m):
    parent, child = map(int, sys.stdin.readline().split())
    graph[parent].append(child)
    graph[child].append(parent)

print(solution(graph, n, start, target))

그래프가 주어졌을 때 시작 노드에서 목적지 노드까지
몇 개의 노드를 거치는지 찾는 문제이다.
(ex - 바로 도달할 수 있으면 1촌, 1개 거쳐가면 2촌)

만약 DFS로 문제를 푼다면 노드의 개수를 카운팅 해가면서
목적지 노드에 도착할 때 카운팅을 반환해 주면 된다.

반면에 BFS로 문제에 접근한다면 목적지가 출발 노드 기준으로
몇 번째 breadth에 속하는지만 판단하면 된다.
그게 더 간단하다고 생각했기 때문에 이번 문제에서는 BFS로 풀이를 진행해 봤다.