[백준] 18352. 특정 거리의 도시 찾기 - 파이썬

 

풀이.

bfs를 이용해서 풀었다.

양방향 그래프이지만 최단거리를 구하는 문제이기때문에 왕복을 한다면 최단거리가 아니다.

따라서 bfs를 이용하여서 해당 도시를 방문했는지 확인을 하고 거리를 구한다.

 

소스코드.

 

	from collections import deque
	import sys
	def bfs(start):
	queue = deque([start])
	while queue:
	now = queue.popleft()
	for next in graph[now]:
	if visited[next] == -1:
	visited[next] = visited[now] + 1
	queue.append(next)
	answer = []
	for i in range(n+1):
	if visited[i] == k:
	answer.append(i)
	answer.sort()
	return answer
	input = sys.stdin.readline
	inf = float('inf')
	n, m, k, x = map(int, input().split())
	graph = [[] for i in range(n+1)]
	visited = [-1] * (n+1)
	visited[x] = 0
	for i in range(m):
	a, b = map(int, input().split())
	graph[a].append(b)
	result = bfs(x)
	if result:
	for i in result:
	print(i)
	else:
	print(-1)

view raw 18352 - 특정 거리의 도시 찾기.py hosted with ❤ by GitHub