BOJ2644 촌수계산

사람 관계 문제는 bfs로 접근해야 풀리는 것 같다. 문제가 익숙치 않아서 다른 분들의 도움을 받아서 풀 수 있게 되었다.

나에게서 멀어질 수록 촌수가 멀어지면 되니까, 큐에 넣을 때 마다 이전 가중치의 + 1을 해준다.

큐에서 구해야 하는 사람의 번호가 나왔을 때는 그 사람의 촌수를 출력해주고 bfs가 끝날때까지 촌수가 없으면 -1 리턴해준다.

from collections import deque

n = int(input())

adj = [[] for _ in range(n+1)]
dist = [0] * (n+1)

me, you = map(int, input().split())

m = int(input())

for _ in range(m):
	u, v = map(int, input().split())
	adj[u].append(v)
	adj[v].append(u)

def bfs():

	q = deque()
	q.append(me)
	while q:
		now = q.popleft()
		if now == you:
			return dist[now]
		for u in adj[now]:
			if dist[u] == 0:
				q.append(u)
				dist[u] = dist[now] + 1
	return -1

print(bfs())