백준 1446번: 지름길 C++ 문제 풀이

📘 백준 1446번: 지름길 C++

📌 문제 설명

세준이는 매일 아침 고속도로를 타고 학교에 갑니다.
이 고속도로는 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번 위치까지 가는 최소 비용을 저장합니다.

dp[0] = 0   // 시작점이므로 비용 0입니다.
dp[1] = ?   // 아직 알 수 없습니다.
dp[2] = ?
...
dp[D] = ?

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

우리는 항상 앞으로만 이동할 수 있으므로
0 → 1 → 2 → ... → D 순서로
하나씩 순서대로 위치를 검사합니다.

각 위치에서 할 수 있는 행동을 확인하여
다음 위치들로 이동할 수 있는지 판단하고,
그에 따른 비용이 더 작다면 갱신합니다.

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

✅ 행동 1: 한 칸 앞으로 걷는 것입니다.

현재 위치가 i라면, 한 칸 앞으로 i + 1로 갈 수 있습니다.
이때 드는 비용은 현재까지의 비용(dp[i]) + 1입니다.

만약 기존에 계산된 dp[i + 1]보다 이 값이 더 작다면,
값을 갱신합니다.

if (dp[i] + 1 < dp[i + 1])
    dp[i + 1] = dp[i] + 1;

✅ 행동 2: 지름길을 타는 것입니다.

지름길 정보 중에 (start = i)인 것이 있다면,
현재 위치에서 그 지름길을 탈 수 있습니다.
이때 목적지는 end이고 비용은 cost입니다.

역시, 계산된 비용이 기존보다 작으면 갱신합니다.

if (start[j] == i && end[j] <= D)
    if (dp[i] + cost[j] < dp[end[j]])
        dp[end[j]] = dp[i] + cost[j];

🧾 4단계. 위 두 가지를 모든 위치에서 반복합니다.

이 과정을 0번부터 D번까지 모든 위치에서 반복합니다.
각 위치마다 걷는 경우, 지름길을 타는 경우를 모두 고려하여
더 짧은 경로가 있다면 갱신합니다.

이 작업이 끝나면, dp[D]에는
0번 위치에서 D번 위치까지 가는 가장 짧은 거리가 저장되어 있게 됩니다.

🧮 상태 정의 및 점화식

✅ 상태 정의

dp[i]는 0번 위치에서 i번 위치까지 이동하는 데 드는 최소 거리입니다.

✅ 점화식 구성

각 위치 i에서 할 수 있는 행동은 다음 두 가지입니다.

1. 한 칸 걷기

if (dp[i + 1] > dp[i] + 1)
    dp[i + 1] = dp[i] + 1;

2. 지름길 사용

if (start[j] == i && end[j] <= D)
    if (dp[end[j]] > dp[i] + cost[j])
        dp[end[j]] = dp[i] + cost[j];

💻 전체 코드

#include <iostream>
using namespace std;

const int INF = 100001;

int main(void)
{
    int N, D;
    cin >> N >> D;

    int start[12], end[12], cost[12];
    for (int i = 0; i < N; i++) {
        cin >> start[i] >> end[i] >> cost[i];
    }

    int dp[10001];
    for (int i = 0; i <= D; i++) dp[i] = INF;
    dp[0] = 0;

    for (int i = 0; i <= D; i++) {
        // 한 칸 걷기
        if (i + 1 <= D && dp[i + 1] > dp[i] + 1)
            dp[i + 1] = dp[i] + 1;

        // 지름길 사용
        for (int j = 0; j < N; j++) {
            if (start[j] == i && end[j] <= D) {
                if (dp[end[j]] > dp[i] + cost[j])
                    dp[end[j]] = dp[i] + cost[j];
            }
        }
    }

    cout << dp[D] << '\n';
    return 0;
}

🔍 코드 상세 리뷰

✅ 1. 입력 처리 및 배열 선언

int start[12], end[12], cost[12];
for (int i = 0; i < N; i++) {
    cin >> start[i] >> end[i] >> cost[i];
}

• 최대 지름길 수가 12개이므로 배열 크기는 12로 선언합니다.
• 각 지름길의 시작점, 끝점, 비용을 별도 배열로 저장합니다.
• 나중에 각 위치를 순회할 때 해당 지점이 지름길 출발점인지 확인하기 위해 사용합니다.

✅ 2. dp 배열 초기화

int dp[10001];
for (int i = 0; i <= D; i++) dp[i] = INF;
dp[0] = 0;

• dp[i]는 0번에서 i번 위치까지 오는 데 드는 최소 거리입니다.
• 모든 값은 큰 수(INF)로 초기화하고, 출발점인 dp[0]만 0으로 설정합니다.

✅ 3. 한 칸 걷는 경우 갱신

if (i + 1 <= D && dp[i + 1] > dp[i] + 1)
    dp[i + 1] = dp[i] + 1;

• 현재 위치 i에서 다음 칸 i + 1로 걸어서 이동합니다.
• 비용은 +1이며, 기존값보다 작으면 갱신합니다.
• 경계 조건(i+1이 D보다 작거나 같은지)을 반드시 확인해야 합니다.

✅ 4. 지름길 사용하는 경우 갱신

if (start[j] == i && end[j] <= D) {
    if (dp[end[j]] > dp[i] + cost[j])
        dp[end[j]] = dp[i] + cost[j];
}

• 현재 위치 i가 지름길 출발점이면,
• 해당 지름길로 도착하는 위치까지 비용을 계산해보고,
• 기존보다 작으면 그 위치의 값을 갱신합니다.

✅ 5. 최종 결과 출력

cout << dp[D] << '\n';

• 목적지 D번 위치까지의 최소 거리 출력입니다.
• 이전까지 모든 경우의 수를 고려한 결과입니다.

✅ 마무리

• 지름길을 포함한 경로 최적화 문제는 누적 최소 거리의 대표적인 예시입니다.
• 각 위치를 왼쪽부터 오른쪽으로 순회하며, 갱신 가능한 경로를 모두 갱신해야 합니다.
• 걷기와 지름길 두 가지 행동을 모두 고려하면, 문제를 정확히 해결할 수 있습니다.