[BOJ][⚪1][백준#01446] 지름길

문제 출처

BAEKJOON Online Judge #1446

문제

매일 아침, 세준이는 학교에 가기 위해서 차를 타고 D킬로미터 길이의 고속도로를 지난다. 이 고속도로는 심각하게 커브가 많아서 정말 운전하기도 힘들다. 어느 날, 세준이는 이 고속도로에 지름길이 존재한다는 것을 알게 되었다. 모든 지름길은 일방통행이고, 고속도로를 역주행할 수는 없다. 세준이가 운전해야 하는 거리의 최솟값을 출력하시오.

입력

첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이가 주어진다. 모든 위치와 길이는 10,000보다 작거나 같은 음이 아닌 정수이다. 지름길의 시작 위치는 도착 위치보다 작다.

출력

세준이가 운전해야하는 거리의 최솟값을 출력하시오.

예제

예제 1

입력

5 150
0 50 10
0 50 20
50 100 10
100 151 10
110 140 90

출력

70

예제 2

입력

2 100
10 60 40
50 90 20

출력

80

예제 3

입력

8 900
0 10 9
20 60 45
80 190 100
50 70 15
160 180 14
140 160 14
420 901 5
450 900 0

출력

432

My Sol

from heapq import heappop, heappush

def dijk(s):
    global D
    visit = [0]*(L+1)
    D[s] = 0
    Q = [[0, s]]

    while Q:
        d, u = heappop(Q)
        if visit[u]: continue
        visit[u] = 1

        for v, w in G[u]:
            if not visit[v] and D[v] > D[u]+w:
                D[v] = D[u]+w
                heappush(Q, [D[v], v])


N, L = map(int, input().split())
D = [L+1]*(L+1)
G = [[] for _ in range(L+1)]
for _ in range(N):
    s, e, w = map(int, input().split())
    if e > L: continue
    G[s].append([e, w])

for i in range(L):
    G[i].append([i+1, 1])

dijk(0)
print(D[L])

다익스트라 알고리즘을 이용해 푸는 문제였는데, 다익스트라는 양방향이었다면, 고속도로는 역주행할 수 없으니 단방향으로 가중치를 추가하는 부분이었다. 다익스트라 알고리즘 템플릿을 참고하였다.

다익스트라 알고리즘은 visit을 이용해 방문하지 않았던 곳만 방문한다. 최초 시작점의 좌표와 가중치를 우선순위 큐에 넣고, Q가 존재하는동안 while문을 반복해준다.

기준점과 연결된 정점의 좌표와 가중치를 모두 조회하는데, 각 정점의 가중치는 시작점으로부터의 최소 거리를 의미하며, 고속도로는 L을 넘는 거리를 가질 수 없으므로 L+1로 초기화해주었다. 만약 기준점으로부터의 거리 w와 시작점부터 기준점까지의 거리 D[u]를 더한 값이 기존에 시작점부터 정점까지의 거리 D[v]보다 짧다면 최소거리가 갱신되는 것이므로 이를 D[v]로 지정하고 Q에 D[v]를 가중치로, v를 기준점으로 추가해준다.

결과

맞았습니다!!

모범답안

출처

import sys
input = sys.stdin.readline

N, D = map(int, input().strip().split())
dis = [0]*10001
short = [list(map(int, input().strip().split())) for _ in range(N)]

short.sort()

for i in range(1, D+1):
  dis[i] = dis[i-1]+1
  for s, e, d in short:
    if i == e:
      dis[e] = min(dis[e], dis[s]+d)

print(dis[D])

백준 채점 현황에서 발견한 짧은 풀이이다.

dp에 가까운 방식으로 문제를 푸셨는데, 거리 배열을 dis로 두고 인덱스가 최대 10000이 될 수 있도록 10001로 두셨다. 그리고 1부터 D까지 for문을 돌며 기본적으로 지름길을 통하지 않았을 때의 거리를 매번 지정하고, 지름길 리스트의 시작점, 도착점, 거리를 보며 도착점이 같을 때 시작점의 거리와 지름길 길이를 더한 값과, 시작점부터 도착점까지의 거리 중 최솟값을 다시 도착점 좌표에 저장하였다.