백준 문제풀이
2644번 - 촌수계산 / silver 2 / BFS
RonLee
2023. 1. 5. 17:55
https://www.acmicpc.net/problem/2644
2644번: 촌수계산
사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어
www.acmicpc.net
'''
2644번 - 촌수계산 / silver 2 / BFS
'''
import sys
from collections import deque
input = sys.stdin.readline
def bfs(start, end, arr, visited):
find_flag = False
que = deque()
que.append((start, 0))
visited[start] = True
while que:
node, res = que.popleft()
if node == end:
find_flag = True
print(res)
for next_node in arr[node]:
if not visited[next_node]:
que.append((next_node, res + 1))
visited[next_node] = True
if not find_flag:
print(-1)
n = int(input())
a, b = map(int, input().split())
arr = [[] for _ in range(n + 1)]
m = int(input())
for _ in range(m):
x, y = map(int, input().split())
arr[x].append(y)
arr[y].append(x)
visited = [False] * (n + 1)
bfs(a, b, arr, visited)