CS/Algorithm
[BOJ/Python] 백준 2644번 - 촌수계산
sohy
2022. 9. 18. 23:41
백준 #2644 촌수계산
2644번: 촌수계산
사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어
www.acmicpc.net
from collections import deque
import sys
input = sys.stdin.readline
def bfs():
q = deque()
q.append(p1)
while(q):
u = q.popleft()
if u == p2:
return visited[p2]
for w in family[u]:
if visited[w] == 0:
if w == p1:
continue
visited[w] = visited[u] + 1
q.append(w)
n = int(input()) # 사람의 수
p1, p2 = map(int, input().split()) # 촌수 계산할 서로 다른 두 사람의 번호
m = int(input()) # 부모 자식들 간의 관계의 개수
family = [[] for _ in range(n+1)]
for _ in range(m):
v1, v2 = map(int, input().split())
family[v1].append(v2)
family[v2].append(v1)
visited = [0 for _ in range(n+1)]
cnt = bfs()
if cnt:
print(cnt)
else:
print(-1)너비우선탐색으로 최단경로 길이만 계산하면 되는 문제! 촌수를 계산할 시작 번호에서 끝 번호가 나올 때까지 탐색을 진행하여 이동 횟수를 visited 리스트에 담아준다. 끝 번호가 나오면 이동 횟수 return
