백준 2644 문제 풀이

🐒 촌수계산

https://www.acmicpc.net/problem/2644

✍ 나의 풀이

from collections import deque


n = int(input())
a, b = map(int, input().split())
m = int(input())

graph = [[] for _ in range(n+1)]
visited = [0] * (n+1)

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

def bfs(a):
    queue = deque()
    queue.append(a)
    
    while queue:
        x = queue.popleft()
        if x == b:
            return visited[x] 
        for i in graph[x]:
            if visited[i] == 0:
                queue.append(i)
                visited[i] = visited[x] + 1
    return -1

print(bfs(a))

12분 걸림 굿

🧠 문제 이해

일단 예제에 나온 촌수를 직접 종이에 그려보니 트리구조가 보였고,
이전에 무방향 그래프 만드는 법을 배웠기 때문에
bfs를 이용하여 연결된 노드를 탐색하면서 1씩 더해주다가
대상을 발견하면 촌수를 출력하고, 탐색이 끝나도 대상을 찾지 못하면 -1을 출력한다.