[BaekJoon 1446 : 다익스트라, Python] - 지름길

2021, Nov 04    


백준 1446 지름길 : 실버 1



Solution


1. 짧은 풀이


다익스트라 알고리즘으로 분류되었지만, 풀이 방식은 전형적인 다익스트라와 조금 다르다.
어차피 노드 수가 많지 않기 때문에 (< 10,000) 굳이 최소거리 노드를 반환하는 heapq 를 쓰지 않고 for 문을 처음부터 다 도는 풀이이다.
heapq 를 정렬하는 데 드는 O(logn) 만큼의 시간이 안 걸렸고 + for 문을 도는 데 많은 시간이 걸리지 않았기 때문에 실제 코드를 돌리는 데 소요시간은 아래 정석적인 다익스트라를 활용한 풀이와 거의 비슷했다.


import sys
n, total = map(int, input().split())
graph = []
dist = [i for i in range(total+1)]
for _ in range(n):
    s, e, d = map(int, sys.stdin.readline().split())
    graph.append((s, e, d))


for i in dist:
    if i != 0:
        for s, e, d in graph:
            if i == e:     
                dist[i] = min(dist[i], dist[s] + d)
        dist[i] = min(dist[i], dist[i-1]+1)

print(dist[-1])


2. 정석적인 DIKJSTRA

전형적인 다익스트라 풀이 구조를 사용해서 풀었다. 데이터 자체가 크지 않아서 heapq 정렬 과정에서 소요되는 시간이 힙이 최소간선만 반환하는 데서 오는 이득을 상쇄시킨 거 같다.


import sys
from collections import defaultdict
from heapq import *
sys = sys.stdin.readline

n, d = map(int, input().split())
graph = defaultdict(list)          # 0~150, default : 자기 노드 + 1 과 연결되어 있음
for i in range(d):
    graph[i].append([i+1, 1])    # connected node, weight

for _ in range(n):
    s, e, l = map(int, input().split()) 
    if e <= d:
        graph[s].append([e, l])         # 지름길로 연결된 노드도 추가

mindist = [float('inf') for _ in range(d+1)]       
hq = []
heappush(hq, [0, 0])  # 현재 노드까지 오면서 누적된 wgt, node

while hq:
    cur_w, cur_n = heappop(hq)
    if mindist[cur_n] < cur_w: continue     # 더이상 작아질 수 없음
    
    for nxt_n, nxt_w in graph[cur_n]:
        dist = cur_w + nxt_w
        if mindist[nxt_n] > dist:
            mindist[nxt_n] = dist
            heappush(hq, [mindist[nxt_n], nxt_n])       # else : 이미 더 작은 거리로 힙큐에 들어가 있음

print(mindist[d])


풀이과정 및 느낀점


위에서 설명한 것처럼 두 가지 풀이로 전개될 수 있고, 두 풀이 간에 시간차이는 얼마 나지 않는다.
이 문제를 풀 때 주의해야 할 점은,

  • 일방통행이다.
  • 모든 도로상의 위치는 정수로 표현 됨.
  • 그리디가 아님. 지름길이라고 무조건 선택 X (나중에 더 빠른 지름길이 나올 수도 있음)
# BaekJoon # Python # dikjstra # 다익스트라 # 그래프 # Algorithm