[Baekjoon 18352 / python / 실버2] 특정 거리의 도시 찾기

import heapq

import sys

INF = int(1e9)

input = sys.stdin.readline

N, E, K, start = map(int, input().split())  # 노드, 간선, 찾을거리, 출발노드

graph = [[] for _ in range(N + 1)]

for _ in range(E):

    a, b = map(int, input().split())  # 출발노드, 도착노드

    graph[a].append([1, b])  # 거리(1), 도착노드

distance = [INF] * (N + 1)

def dijkstra(start):

    queue = []

    heapq.heappush(queue, (0, start))  # 시작노드거리, 시작노드 큐에 삽입

    distance[start] = 0  # 시작노드 최단거리 입력

    result = []

    while queue:

        dist, here = heapq.heappop(queue)

        if distance[here] < dist:  # 기존 최단경로가 지금 가져온 거리보다 짧다면 패스

            continue

        for i in graph[here]: # 현재노드 인접노드정보 가져오기

            cost = dist + i[0]  # 최단거리 + 다음노드까지 거리 계산

            if cost < distance[i[1]]:  # 계산한 게 최단거리라면 최단경로 테이블 갱신

                distance[i[1]] = cost

                if cost == K: result.append(i[1])  # K와 일치하면 결과 리스트에 넣기

                heapq.heappush(queue, (cost, i[1]))  # 갱신했으니 큐에 넣기

    return result

result = dijkstra(start)

result.sort()

if len(result) >= 1:  # K와 일치하는 노드가 존재하면 출력

    for i in result:

        print(i)

else:

    print(-1)

 

다익스트라 알고리즘을 사용하여 풀 수 있는 문제이다.

 

그냥 다익스트라 알고리즘 코드를 때려 넣기만 하면 매우 쉽게 풀 수 있다. 물론 그걸 공부하는 게 문제지만...

만약 다익스트라를 모르는데 이 문제를 풀려고 한다면, 그냥 포기하고 구글링해서 다익스트라를 먼저 공부하는 걸 추천한다.

 

다익스트라 알고리즘은 최단 경로 알고리즘이라고도 하는데, 시작 노드부터 특정 노드까지의 최단 거리를 계산할 수 있는 알고리즘이다. 우선순위 큐를 쓰기 때문에 heapq 최소 힙을 사용해서 구현한다. 다익스트라에 대한 설명은 https://yskisking.tistory.com/185

내 블로그 글에서도 볼 수 있고, 설명을 잘 해놓은 분들이 워낙 많으니 찾아보길 추천한다.