[Coding Test][Python][백준] BOJ #1466 지름길

 

 

 

# 1446 지름길

문제)

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

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

입력)

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

다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이가 주어진다. 모든 위치와 길이는 10,000보다 작거나 같은 음이 아닌 정수이다. 지름길의 시작 위치는 도착 위치보다 작다.

출력)

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

---

풀이)

※ 풀이 아이디어

문제를 보면 최단 거리 문제라는 것을 알 수 있다.
거리는 모두 양수이므로 다익스트라(Dijkstra) 알고리즘을 이용하여 풀면 된다.
    고속도로의 위치를 Node로 보고, 지름길을 Edge로 표현한다.
또한, DP를 통해 풀이할 수 있다.
    DP Table을 "고속도로의 특정 지점까지 가는 최단거리"로 정의하면 된다.
    이전 거리에서 +1을 하거나, 지름길을 활용해 최소값을 갱신한다.

 

다익스트라 알고리즘과 DP 알고리즘에 대한 글은 아래 글에서 확인할 수 있습니다.

다익스트라 알고리즘

[Coding Test][Python][Shortest Path] Dijkstra Algorithm(다익스트라) 개념 및 예제

DP 알고리즘

[Coding Test][Python] Dynamic Programming(DP) 개념 및 예

1) Dijkstra를 이용한 풀이

from collections import defaultdict
import heapq

N, D = map(int, input().split())
INF = float('inf')
distances = [INF] * (D+1)

roads = defaultdict(list)

# i -> i+1 의 dist는 1
for i in range(D):
    roads[i].append((i + 1, 1))

# 지름길 정보
for _ in range(N):
    u, v, shortcut_dist = map(int, input().split())
    if v <= D:  # 도착 지점이 D를 넘어가면 무시
        roads[u].append((v, shortcut_dist))

# 다익스트라 알고리즘
def dijkstra(start):
    pq = [(0, start)]  
    heapq.heapify(pq)
    
	# 시작점 거리 0
    distances[start] = 0  

    while pq:
        curr_dist, curr_pos = heapq.heappop(pq)

        # 이미 더 짧은 경로가 있을 경우
        if curr_dist > distances[curr_pos]:  
            continue

        # 현재 위치에서 이동 가능한 경로 탐색
        for next_pos, next_dist in roads[curr_pos]:
            total_dist = curr_dist + next_dist
            
            if total_dist < distances[next_pos]:
                distances[next_pos] = total_dist
                heapq.heappush(pq, (total_dist, next_pos))

# 다익스트라 실행
dijkstra(0)

# 최단 거리 출력
print(distances[D])

 

문제를 풀다 잘 풀리지 않아 풀이를 찾아보니 아래 코드를 추가해주어야 풀이가 가능했다.

이는 일반 도로를 연결하여 지름길이 없을 경우에 대한 경로를 추가한 코드이다.

일반 도로를 연결해야하는 이유는 아래와 같다.

for i in range(D):
    roads[i].append((i + 1, 1))

[0, 4, 2], [4, 9, 3] [10, 15, 4]의 지름길이 있다고 하자.(도착점 15)
일반 도로를 연결하지 않은 경우
    - 0 -> 4 비용 2
    - 4 -> 9 비용 3
    - 하지만 9 -> 10을 갈 수 있는 경로가 없기 때문에 문제가 풀리지 않는다.
    - 또한, 도착점인 15로 갈 수 있는 경로도 존재하지 않다
일반 도로를 연결한 경우
    - 0 -> 4 비용 2
    - 4 -> 9 비용 3
    - 9 -> 10 비용 1
    - 10 -> 15 비용 4
일반 도로를 연결하는 코드를 통해 지름길이 없는 구간에서도 정상적으로 이동할 수 있다.

2) DP를 이용한 풀이

from collections import defaultdict

N, D = map(int, input().split())
INF = float('inf')

# 초기값: i번째 위치까지 가는 기본 거리 (i)
dp = [i for i in range(D + 1)]  

roads = defaultdict(list)

for _ in range(N):
    u, v, shortcut_dist = map(int, input().split())
    if v <= D:  # 도착 지점이 D를 넘어가면 무시
        roads[u].append((v, shortcut_dist))

for i in range(D + 1):
    # i까지 일반 도로로 도착하는 경우
    if i > 0:
        dp[i] = min(dp[i], dp[i - 1] + 1)

    # i에서 출발하는 지름길이 있다면, 더 짧은 거리로 갱신
    # roads의 key는 지름길의 start pos
    if i in roads:
        for end, dist in roads[i]:
        	# dp[end] : 일반도로로 가는 경로 또는 길이가 더 긴 지름길을 통한 경로
            dp[end] = min(dp[end], dp[i] + dist)

# 최단 거리 출력
print(dp[D])

 

도착점은 15이고 [0, 4, 2], [4, 9, 3] [10, 15, 4]의 지름길이 있다고 할 때 DP의 동작과정은 아래의 그림과 같습니다.

i = 0 일때 입니다.

출발점이 0일때 지름길이 존재하므로 아래 코드에 따라 dp[4]가 update 됩니다.

if i in roads:
    for end, dist in roads[i]:
        dp[end] = min(dp[end], dp[i] + dist)

i = 0 일때 입니다.

출발점이 4일때 지름길이 존재하므로 dp[9]가 update 됩니다.

그 후 i가 5, 6,  7, 8이 되었을 때 아래 코드에 따라 Table의 update 되게 됩니다.

if i > 0:
    dp[i] = min(dp[i], dp[i - 1] + 1)