[백준] 2644번: 촌수계산

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

2644번: 촌수계산

코딩테스트 전 이전에 공부한 bfs 개념을 되돌아보기 위해 풀어보았다.

 

deque를 사용하여 popleft를 사용할 수 있게하였다.

from collections import deque

answer = -1
flag = 0
n = int(input());
start, end = map(int,input().split());
m = int(input());

arr = [[0 for i in range(n+1)]for j in range(n+1)]

for i in range(0,m):
    x,y = map(int,input().split());
    arr[x][y] = 1;
    arr[y][x] = 1;


q = deque([])

for i in range(1,n+1):
    if arr[start][i] == 1:
        q.append([start,i,0])
# 0부터시작이 아니라 1부터 시작
while q:
    # print(q)
    # print()
    x , y, cnt = q.popleft();
    if y == end:
        answer = cnt+1
        break
    for i in range(1,n+1):
        if arr[y][i] == 1 and i!=x:
            q.append([y,i,cnt+1])

print(answer)