[BOJ] 1854번 K번째 최단경로 찾기 / 사용언어 : 파이썬(python)

※ 문제링크

1854번: K번째 최단경로 찾기

해당문제는 다익스트라를 활용하여 풀 수 있는 문제였다. 가중치가 있는 최단경로를 구하는 문제에서 조금 더 나아간 문제로, 간선으로 이어져있는 도시들을 k번째 수가 구해질때까지만 반복시키는 것이 핵심인 문제였다. 해당 부분은 메모이제이션과 정렬을 반복함으로써 해결하였으며, 테스트 결과 정상적으로 작동하는 것으로 확인했다. 다만, sys를 사용하고도 3528ms가 걸리는 것으로 확인했기에 sys를 사용하지 않으면 통과가 되지 않을 수도 있으니 유의해야 할 것 같다. 자세한 풀이방법과 코드는 아래와 같다.

1. 입력받은 값들을 리스트를 활용하여 그래프를 구현해준다.

2. k번째로 짧은 경로를 확인할 수 있는 2차원 리스트를 만들어 주고, 최단경로를 지속적으로 탐색할 다익스트라 알고리즘을 만든다.

3. 함수에 입력값을 넣고 결과값이 나올 때까지 동작시킨 후 sys를 활용하여 결과값을 출력해준다.

+ 유의해야할 점 : 해당 문제는 같은 시간이 걸리는 경로가 여러개 나올 수 있다. 특정한 값이 여러개 나온다 해도 중복제거를 해주면 안되고, 하나의 고유한 값으로 생각해야한다.(set으로 중복제거를 해주면 틀리게 됩니다.)

 

import sys
from heapq import heappush, heappop

def dijkstra(start):
    heap = []
    heappush(heap, [0, start])
    dp[start][0] = 0

    while heap:
        n_t, t_c = heappop(heap)
        for t_c_t, s_o in graph[t_c]:
            s_t = n_t + t_c_t
            if dp[s_o][k-1] > s_t:
                dp[s_o][k-1] = s_t
                dp[s_o].sort()
                heappush(heap, [s_t, s_o])

# input = sys.stdin.readline
n, m, k = map(int, input().split()) # n: 도시의 수 / m: 도로의 수
graph = [[] for _ in range(n+1)]
dp = [[float('inf') for _ in range(k)] for _ in range(n+1)]
for _ in range(m):
    s, e, t = map(int, input().split())
    graph[s].append([t, e])

dijkstra(1)
for i in range(1, n+1):
    value = dp[i]
    if i == n:
        if value[k-1] == float('inf'):
            sys.stdout.write(f'{-1}')
        else:
            sys.stdout.write(f'{dp[i][k-1]}')
    else:
        if value[k-1] == float('inf'):
            sys.stdout.write(f'{-1}\n')
        else:
            sys.stdout.write(f'{dp[i][k-1]}\n')

 

P.S 더 나은 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.