문제

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

나의 코드 (답안 참조)

"""
1. 아이디어
예제에 대한 트리를 직접 그려보고 문제에 접근하자.
일단 촌수를 건너갈때 마다 카운트를 해줘야 하므로 (노드, 카운트) 형식의 튜플형태로
bfs를 돌리면서 반복문 내에 조건식을 써서 만약 찾고자 하는 노드를 찾으면 카운트한 횟수를
return 하는 형식으로 작성하자

2. 시간복잡도
O(N)
"""

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

n = int(input())
x, y = map(int, input().split())
m = int(input())
tree = [ [] for _ in range(n+1) ]
visited = [False] * (n+1) # 방문한 곳을 또 방문하면 카운트가 초기화 되니깐 방문여부 체크.
answer = -1 # 만약 노드가 일치하지 않으면 -1을 출력해야 하므로 미리 -1로 초기화.

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

def bfs(x):
    global answer
    q = deque([(x, 0)])

    while q:
        node, cnt = q.popleft()

        if node == y: # 만약 찾고자 하는 노드를 찾으면 카운트한 횟수를 return함.
            answer = cnt

        for i in tree[node]:
            if not visited[i]:
                visited[i] = True
                q.append((i, cnt+1))

bfs(x)

print(answer)
    

느낀점

앞에 문제인 '트리의 부모 찾기'를 혼자 힘으로 풀고 살짝 응용만 할 수 있으면 풀 수 있는 문제 인것 같다.