[코딩테스트][백준] 🔥 백준 1162번 "도로포장" 문제: Python으로 완벽 해결하기! 🔥

문제 링크

https://www.acmicpc.net/problem/1162

🕒 Python 풀이시간: 1시간 30분

import sys
import heapq
input=sys.stdin.readline
INF=10**12

n,m,k=map(int,input().split())
distance=[[INF]*(n+1) for _ in range(k+1)]
graph=[[] for _ in range(n+1)]

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

def dijkstra(start):
    for i in range(0,k+1):
        distance[i][start]=0
    q=[]
    heapq.heappush(q,(0,start,0))

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

        if dist>distance[nowK][now]:
            continue
        
        for i in graph[now]:
            cost=dist+i[1]
            if cost<distance[nowK][i[0]]:
                distance[nowK][i[0]]=cost
                heapq.heappush(q,(cost,i[0],nowK))
            if nowK<k:
                if dist<distance[nowK+1][i[0]]:
                    distance[nowK+1][i[0]]=dist
                    heapq.heappush(q,(dist,i[0],nowK+1))
    
dijkstra(1)
answer=INF
for i in range(0,k+1):
    answer=min(answer,distance[i][n])
print(answer)

최단 거리 문제: 도로 포장 활용! 🛣️✨

도로 포장을 실시하면 최대 K번 횟수만큼 도로의 비용을 0으로 지날 수 있는 최단 거리 문제이다. 다익스트라를 활용하면서 마치 고난이도 BFS처럼 차원을 나눠서 이동하는 문제이다. 이때, 최대 갱신될 수 있는 거리가 1,000,000x50,000인 점에 유의하여야 한다.

기본적인 알고리즘은 다익스트라에서 시작된다. 다익스트라를 실시하되 K번의 사용 횟수에 따라 다른 차원에 최단 거리를 갱신해 나가는 것이다. 이를 생각하면 간단하다. 왜냐하면 비용이 0이기 때문에 현재까지 지점까지의 거리를 그대로 가지고 가고 사용되는 k의 횟수만 +1해서 기록하면 되기 때문이다.

이렇게 Python으로 백준의 "도로포장" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊