[Python/파이썬] - 백준(BOJ) 2644번 : 촌수계산

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

2644번: 촌수계산

 

BFS를 이용해 관계를 탐색하는 문제

부모 - 자식 관계를 arr에 양방향으로 저장한 후

시작 - 끝 관계를 BFS 탐색하며 visit을 1씩 증가시켜준다

루프가 끝났을 때 visit[end]가 0인 경우 알 수 없어 -1을 출력하고,

0이 아닌 경우 시작할 때 본인에 1을 더했으니 visit[end]에 1을 빼서 출력한다

 

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

n = int(input())
start, end = map(int,input().split())
m = int(input())
arr = [[] for _ in range(n+1)]
visit = [0] * (n+1)
for i in range(m):
    s, e = map(int,input().split())
    arr[s].append(e)
    arr[e].append(s)
queue = deque([start])
visit[start] = 1
while queue:
    x = queue.popleft()
    if x == end:
        break
    for y in arr[x]:
        if visit[y] == 0:
            visit[y] = visit[x] + 1
            queue.append(y)
if visit[end] == 0:
    print(-1)
else:
    print(visit[end] - 1)