다익스트라 알고리즘
bfs와 dfs 문제 할당량을 끝내고서 복습 하기 전에, 머리 속에서 dfs와 bfs 문제들을 잊기 위해 또 다른 그래프 알고리즘인 다익스트라 알고리즘을 공부해보았다.
다익스트라 알고리즘은 모든 간선이 양의 가중치를 가질 때에 최단 경로를 구할 수 있는 빠른 알고리즘으로 시간 복잡도는 O(ElogE)(E는 간선 수) 가 된다.
문제 분석
도로를 포장 할 기회가 주어진다는 사실과 다익스트라의 연결고리가 보이지 않아, 모든 포장 가능한 개수에 대한 간선조합을 구하여 각 간선을 포장한 도로에 대해 전부 다익스트라 알고리즘을 적용시키는 방법으로 문제를 풀어봤다. 그러나 역시나 3퍼센트를 넘기지 못하고 시간초과가 나게 되었다.
나는 핵심적인 문제가 제거해야할 간선을 효율적으로 알아내는 것이라고 생각했지만, 그것은 정확한 파악이 아니었다는 사실을 추후에 알게되었다.
실제 문제는 단 한번의 다익스트라 알고리즘을 사용하여 풀 수 있는 문제다. 도로포장의 횟수를 하나의 차원으로 생각하여, 도로 포장 횟수 간의 이동 또한 가능한 삼차원 배열로 문제를 생각하게 되면, 결국 k번 찬스를 썼을 때 도착하는 최단 경로가 한번에 구해지게 된다.
자아성찰
지금 나의 문제는 문제를 한눈에 구조화시키는 능력이 부족하다는 것이다. 결국 아직 컴퓨터 식 사고방식에 익숙해지지 않았다는 결론으로 귀결된다. 해결 방법은 많은 문제를 접하는 것이고, 문제를 풀기에 앞서 어떤 문제인가에 대해 깊이 고민해보는 시간을 늘 갖는다면, 자연히 실력이 늘지 않을까 그렇게 생각한다. 풀이 개념에 대해 들었을 때에 구현하는 것은 쉬운 일이었다. 이제는 사고력을 훈련해야 할 때인 것 같다.
다음은 문제 풀이
import sys
from heapq import heappush, heappop
input = sys.stdin.readline
def solve():
N, M, K = map(int, input().split())
graph = [[(i, 0)] for i in range(N)]
for _ in range(M):
u, v, w = map(int, input().split())
graph[u-1].append((v-1, w))
graph[v-1].append((u-1, w))
visited = [[0]*N for _ in range(K+1)]
dist = [[float('inf')]*N for _ in range(K+1)] # [k][i]
q = []
dist[0][0] = 0
q.append((dist[0][0], 0, 0))
while q:
cw, k, c = heappop(q)
if visited[k][c]:
continue
visited[k][c] = 1
for n, nw in graph[c]:
if not visited[k][n] and dist[k][n] > dist[k][c]+nw:
dist[k][n] = dist[k][c]+nw
heappush(q, (dist[k][n], k, n))
if k < K:
if not visited[k+1][n] and dist[k+1][n] > dist[k][c]:
dist[k+1][n] = dist[k][c]
heappush(q, (dist[k+1][n], k+1, n))
if visited[K][-1]:
break
print(dist[K][-1])
solve()
