[백준] 18352 (실버2)

코끼리코 10번 돌고 문제 읽어도 다익스트라를 활용하는 문제라는 것을 알 수 있다.

다익스트라 문제를 풀기 위해서는, 다익스트라 알고리즘 자체를 외워두는 것이 좋다.
어렵지 않기 때문에 금방 외우지만 또 금방 까먹기 때문에 자주자주 봐줘야하는 유형이다.

# 다익스트라
import heapq
import sys
INF = int(1e9)


def main():
    n, m, k, x = map(int, sys.stdin.readline().split())
    graph = [[] for _ in range(n+1)]

    for _ in range(m):
        a, b = map(int, sys.stdin.readline().split())
        # a번 노드에서 b번 노드로 가는 비용이 1
        graph[a].append([b, 1])
    # dp 테이블 개념, 출발노드로부터의 거리 저장
    distance = [INF] * (n+1)
    distance[0] = 0

    dijkstra(graph, x, distance)

    for i in range(1, n+1):
        if distance[i] == k:
            print(i)
    if k not in distance:
        print(-1)


def dijkstra(graph, start_node, distance):
    q = []
    distance[start_node] = 0
    heapq.heappush(q, (distance[start_node], start_node))

    while q:
        dist, now = heapq.heappop(q)

        for next_node, next_cost in graph[now]:
            cost = dist + next_cost

            if cost < distance[next_node]:
                distance[next_node] = cost
                heapq.heappush(q, (cost, next_node))


main()