Baekjoon18352_특정 거리의 도시 찾기

문제

풀이

이것이 코딩테스트다에 수록되어있는 미로찾기 문제와 유사한 문제로 BFS를 이용하면 풀 수 있다. 이처럼 그래프에서 간선의 비용이 동일할 때 BFS를 이용하면 최단거리를 찾는 문제의 해답에 쉽게 접근할 수 있다.
1. 특정 도시 x를 시적으로 BFS를 수행한다.
2. 특정 도시에서 도달할 수 있는 도시들을 next에 할당한다.
3. next 도시가 -1의 값을 가질 경우 출발지점에서 now 지점의 도시에 도달하는 최단 거리에 1을 더해 next도시에 할당한다.
4. 모든 경우에 대해 BFS를 수행한 뒤에 최단거리가 k인 값들을 오름차순으로 출력하면 된다.

정답 코드

from collections import deque

n, m, k, x = map(int, input().split())

graph = [[] for _ in range(n+1)]
for _ in range(m):
    a, b = map(int,input().split())
    graph[a].append(b)
    

dist = [-1 for _ in range(m+1)]
dist[x] = 0

q = deque([x])
while q:
    now = q.popleft()
    for next in graph[now]:
        if dist[next] == -1:
            dist[next] = dist[now] + 1
            q.append(next)
            
        
check = False
for i in range(1, n+ 1):
    if dist[i] == k:
        print(i)
        check = True

if check == False:
    print(-1)