[Baekjoon] Shortest Path - 18352 특정 거리의 도시 찾기

문제

18352번: 특정 거리의 도시 찾기

 

풀이

BFS나 DFS를 이용하여 모든 도시로 갈 수 있는 최단의 거리를 구한다.

이 후 최단 거리에 도달한 도시만 출력한다.

 

import sys
from collections import deque

INF = 1e9

n, m, k, x = map(int, sys.stdin.readline().rstrip().split())
distance = [INF] * (n + 1)
graph = [[] for _ in range(n + 1)]
for _ in range(m):
    a, b = map(int, sys.stdin.readline().rstrip().split())
    graph[a].append((b, 1))


def bfs(start, distance, graph, k):
    queue = deque([])
    queue.append((start, 0))
    distance[start] = 0

    while queue:
        now, dist = queue.popleft()

        for v in graph[now]:
            cost = dist + v[1]

            if distance[v[0]] > cost:
                distance[v[0]] = cost
                queue.append((v[0], cost))

    return [i for i in range(1, n + 1) if distance[i] == k] or [-1]


for value in sorted(bfs(x, distance, graph, k)):
    print(value)

 

채점 결과