문제
접근
문제를 읽었을 때 처음 든 생각은 트리구조였다.
하지만 트리구조로 이 문제를 해결하고자 하면, 굉장히 문제가 까다로워진다.
단순히 a노드에서 BFS를 이용하여 b 노드를 방문하는데 걸린 거리를 구하면 문제는 간단하게 해결된다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
from collections import deque
def bfs(start, end):
q = deque()
q.append(start)
visit[start] = 0
while q:
node = q.popleft()
for nxt in adj[node]:
if visit[nxt] == -1:
visit[nxt] = visit[node]+1
q.append(nxt)
n = int(input())
a, b = map(int, input().split(' '))
m = int(input())
adj = [[] for _ in range(n+1)]
visit = [-1] * (n+1)
for i in range(m):
x, y = map(int, input().split(' '))
adj[x].append(y)
adj[y].append(x)
bfs(a, b)
print(visit[b])