알고리즘
[백준] 2644번: 촌수계산
초코비23
2022. 3. 22. 11:40
https://www.acmicpc.net/problem/2644
2644번: 촌수계산
사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어
www.acmicpc.net
코딩테스트 전 이전에 공부한 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)