백준1446, 지름길 Python

📘 백준 1446번: 지름길 Python

📌 문제 설명

세준이는 매일 아침 고속도로를 타고 학교에 갑니다.
이 고속도로는 0번 위치부터 D번 위치까지 이어진 직선 도로입니다.
고속도로는 단방향이며, 차는 매 순간 오직 앞으로만 이동할 수 있습니다.

그런데 이 고속도로에는 지름길이 존재한다고 합니다.
지름길은 특정 위치에서 출발하여, 더 먼 위치로 곧장 이동할 수 있는 특수한 경로입니다.
각 지름길은 시작점, 도착점, 그리고 해당 구간을 이동하는 데 드는 거리(비용)가 주어지며,
기존의 고속도로보다 비용이 작을 수도 있고, 아닐 수도 있습니다.

지름길은 단방향이며, 역주행은 절대 불가능합니다.
우리는 이 지름길과 일반 도로를 조합하여,
0번 위치에서 D번 위치까지 이동하는 최소 거리를 구해야 합니다.

🧾 입력 형식

• 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어집니다.
• 둘째 줄부터 N개의 줄에 걸쳐 지름길의 정보가 주어집니다.
  각 지름길은 시작 위치, 도착 위치, 거리(cost)로 구성됩니다.

제한 사항

• 1 ≤ N ≤ 12
• 1 ≤ D ≤ 10,000
• 모든 위치와 거리는 10,000 이하의 자연수입니다.
• 시작 위치는 항상 도착 위치보다 작습니다.
• 도착 위치가 D보다 크면 무시해도 됩니다.

💡 문제 풀이 아이디어

✅ 이 문제는 '길 찾기' 문제입니다.

우리는 숫자 0번 위치에 서 있습니다.
목표는 숫자 D번 위치에 도착하는 것입니다.
갈 수 있는 방법은 두 가지뿐입니다:

① 방법 1: 한 칸씩 걷는 방법입니다.

0에서 1, 1에서 2, 2에서 3...
이렇게 계속 한 칸씩 앞으로 갈 수 있습니다.
한 칸 이동하는 데 드는 비용은 1입니다.

즉, 아무 지름길도 타지 않고 그냥 +1만 계속 하면서 D까지 가면
총 비용은 D가 됩니다.

② 방법 2: 지름길을 타는 방법입니다.

예를 들어, “0에서 50까지 가는 지름길이 있고, 비용은 10”이라고 주어졌다면,
원래대로라면 0부터 1, 2, 3, ..., 50까지 50칸을 걸어야 하므로 비용이 50이 들지만,
지름길을 타면 단 10만에 50번 위치까지 갈 수 있습니다.

지름길은 다음과 같은 정보로 주어집니다:

(start 위치, end 위치, cost 비용)

이는 "start 위치에서 시작해서 end 위치까지 cost만큼 들고,
중간을 생략하고 바로 이동할 수 있다"는 의미입니다.

✅ 중요한 사실

어떤 위치까지 가는 데는 경로가 여러 개 존재할 수 있습니다.

예를 들어, 50번 위치까지 가는 방법은 다음과 같습니다:

• 0 → 1 → 2 → ... → 50 (비용: 50)
• 지름길 사용: 0 → 50 (비용: 10)
• 다른 지름길 조합: 0 → 30 (비용: 8), 그 후 31 → ... → 50

즉, 같은 위치에 도착하더라도, 어떤 경로로 갔느냐에 따라 비용이 다릅니다.

따라서 우리는 각 위치까지 도달하는 "가장 저렴한 비용"만 저장해야 합니다.

🎯 그러면 이 문제를 어떻게 풀어야 할까요?

🧾 1단계. 각 위치까지 가는 최소 비용을 저장할 상자를 준비합니다.

숫자 0부터 D까지 총 D+1개의 위치가 있으므로
dp[i] 라는 이름의 배열을 만들어서
i번 위치까지 가는 최소 비용을 저장합니다.

🧾 2단계. 0번부터 D번까지 차례로 훑으면서 이동합니다.

왼쪽에서 오른쪽으로 이동하면서
각 위치에서 할 수 있는 행동(걷기, 지름길 타기)을 모두 시도합니다.

🧾 3단계. 각 위치에서 할 수 있는 행동은 딱 두 가지입니다.

• 한 칸 앞으로 이동
• 지름길 사용

각 경우에 대해 dp 값을 비교하여
더 작으면 갱신하는 방식으로 계산합니다.

🧾 4단계. 최종적으로 dp[D]에 최소 비용이 저장됩니다.

🧮 상태 정의 및 점화식

dp[i]: 0번 위치에서 i번 위치까지 가는 최소 거리입니다.

점화식

dp[i + 1] = min(dp[i + 1], dp[i] + 1)  # 걷기
dp[end] = min(dp[end], dp[i] + cost)  # 지름길

💻 전체 코드 (Python)

INF = 100001

N_D = input().split()
N = int(N_D[0])
D = int(N_D[1])

start = [0] * 12
end = [0] * 12
cost = [0] * 12

for i in range(N):
    temp = input().split()
    start[i] = int(temp[0])
    end[i] = int(temp[1])
    cost[i] = int(temp[2])

dp = [INF] * (D + 1)
dp[0] = 0

i = 0
while i <= D:
    if i + 1 <= D:
        if dp[i] + 1 < dp[i + 1]:
            dp[i + 1] = dp[i] + 1

    j = 0
    while j < N:
        if start[j] == i and end[j] <= D:
            if dp[i] + cost[j] < dp[end[j]]:
                dp[end[j]] = dp[i] + cost[j]
        j = j + 1

    i = i + 1

print(dp[D])

🔍 코드 상세 리뷰

🔸 상수 정의 및 기본 입력 처리

INF = 100001

• 최댓값처럼 사용할 수 있는 충분히 큰 수입니다.
• 모든 위치의 최소 비용을 저장할 때 초기값으로 사용됩니다.

N_D = input().split()
N = int(N_D[0])
D = int(N_D[1])

• 첫 줄에서 지름길의 수 N과 고속도로의 길이 D를 입력받습니다.
• input().split()으로 공백 기준 분리 후, 각각 정수로 변환합니다.

🔸 지름길 정보 저장

start = [0] * 12
end = [0] * 12
cost = [0] * 12

• 최대 12개의 지름길이 주어지므로 배열 크기를 12로 고정합니다.
• 각 지름길의 시작점, 도착점, 비용을 따로 저장합니다.

for i in range(N):
    temp = input().split()
    start[i] = int(temp[0])
    end[i] = int(temp[1])
    cost[i] = int(temp[2])

• N개의 지름길 정보를 한 줄씩 입력받아 각각 배열에 저장합니다.
• 리스트 컴프리헨션 없이 단순 for문으로 작성되었습니다.

🔸 dp 배열 초기화

dp = [INF] * (D + 1)
dp[0] = 0

• dp[i]는 위치 i까지 오기 위한 최소 비용을 저장합니다.
• 0번 위치는 출발점이므로 비용은 0입니다.
• 나머지 값들은 모두 INF로 초기화합니다.

🔸 위치 0부터 D까지 순차 탐색

i = 0
while i <= D:

• 현재 위치 i를 0부터 D까지 하나씩 순회합니다.
• 이 반복문 내에서 걷기와 지름길 두 가지 갱신을 처리합니다.

🔸 행동 1: 한 칸 걷기

    if i + 1 <= D:
        if dp[i] + 1 < dp[i + 1]:
            dp[i + 1] = dp[i] + 1

• 현재 위치 i에서 다음 위치 i+1로 한 칸 걷는 경우입니다.
• 비용은 현재까지 비용 dp[i]에 1을 더한 값입니다.
• 이 값이 dp[i+1]보다 작을 경우 갱신합니다.

🔸 행동 2: 지름길 사용

    j = 0
    while j < N:
        if start[j] == i and end[j] <= D:
            if dp[i] + cost[j] < dp[end[j]]:
                dp[end[j]] = dp[i] + cost[j]
        j = j + 1

• 모든 지름길을 순회하며, 현재 위치 i가 지름길 출발점인지 확인합니다.
• 해당 지름길을 이용한 비용이 기존보다 작으면 갱신합니다.

🔸 인덱스 증가 및 최종 출력

    i = i + 1

print(dp[D])

• 현재 위치를 1 증가시키며 다음 위치를 처리합니다.
• 최종적으로 dp[D]에 저장된 최소 비용을 출력합니다.

✅ 마무리

• 지름길 사용 여부에 따라 동적으로 최소 비용을 갱신합니다.
• 0번부터 D번까지 순차적으로 접근하면서, 각 위치에서 가능한 행동(걷기 / 지름길 사용)을 모두 시도합니다.
• 최종적으로 가장 짧은 경로가 dp[D]에 저장되어 출력됩니다.