-
[Python 3] BOJ - 1162 "도로포장"BOJ 2021. 8. 30. 12:07
# 문제 링크
https://www.acmicpc.net/problem/1162
# 풀이
개인적으로 이 문제의 핵심은 2차원 다익스트라 알고리즘이라고 생각한다. 일반적으로 다익스트라 알고리즘은 1차원 배열이지만, 이 문제에는 정점과 또 다른 정보인 포장 횟수가 있으며 포장 여부에 따라 간선의 가중치가 달라지기 때문에 1차원으로 설정한다면 포장에 대한 정보를 알 수 없다. 따라서, 포장을 시키지 않는 경우를 기본적으로 검사한 후, 포장할 여력이 있다면 포장을 시키면서 최소 거리를 찾으면 정답을 구할 수 있다.
# 코드
import sys, heapq # 입력부 n,m,k = map(int, sys.stdin.readline().split()) adj = [[] for _ in range(n + 1)] for _ in range(m): a,b,c = map(int, sys.stdin.readline().split()) adj[a].append((b,c)) adj[b].append((a,c)) # inf : 임의의 무한대값 inf = 98765432109876543210 # d : 2차원 다익스트라 배열. 현재 정점 i에서 포장을 j개 했을 때 드는 최소거리 d = [[inf] * (k + 1) for _ in range(n + 1)] q = [] for i in range(k + 1): d[1][i] = 0 heapq.heappush(q, (0,1,0)) # 다익스트라 while q: now_dist, now, p = heapq.heappop(q) if d[now][p] < now_dist: continue # 현재 정점에서 포장이 가능한 경우 if p + 1 <= k: for (next, next_dist) in adj[now]: if d[next][p + 1] > now_dist: d[next][p + 1] = now_dist heapq.heappush(q, (now_dist, next, p + 1)) # 기본적으로 포장을 하지 않는 경우 for (next, next_dist) in adj[now]: if d[next][p] > now_dist + next_dist: d[next][p] = now_dist + next_dist heapq.heappush(q, (now_dist + next_dist, next, p)) # 정답 출력 ans = inf for i in range(k + 1): ans = min(ans, d[n][i]) print(ans)
'BOJ' 카테고리의 다른 글
[Python 3] BOJ - 17619 "개구리 점프" (0) 2021.09.01 [Python 3] BOJ - 5721 "사탕 줍기 대회" (0) 2021.08.31 [Python 3] BOJ - 2151 "거울 설치" (0) 2021.08.26 [Python 3] BOJ - 1933 "스카이라인" (0) 2021.08.25 [Python 3] BOJ - 1700 "멀티탭 스케줄링" (0) 2021.08.24