[백준] 1446번: 지름길

https://www.acmicpc.net/problem/1446

1446번: 지름길

크게 2가지 방식으로 문제를 풀어보았다.

첫 번째는 최소 길이를 구하는 만큼 다익스트라 알고리즘으로,

두 번째는 문제의 목적에 더 부합하는 풀이 방식인 다이나믹 프로그래밍으로 풀었다.

 

다익스트라의 경우 약간의 변형이 필요하다.

이웃한 점은 서로 인접, 연결되어있다는 가정 하에 한 차례 갱신이 더 필요하다.

 

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
vector<vector<pair<int,int>>> shortcut(10000);
vector<int> dist(10000, 10000);
priority_queue<int> q;

int main() {
    int N, D;
    cin >> N >> D;
    for(int i = 0;i < N;i++) {
        int a, b, d;
        cin >> a >> b >> d;
        shortcut[a].push_back({b, d});
    }
    
    dist[0] = 0;
    q.push(0);
    while(!q.empty()) {
        int pos = q.top();
        q.pop();
        if (pos >= D) continue;
        for(int i = 0;i < shortcut[pos].size();i++) {
            int next_pos = shortcut[pos][i].first;
            int part_dist = shortcut[pos][i].second;
            
            if(dist[next_pos] > dist[pos] + part_dist) {
                dist[next_pos] = dist[pos] + part_dist;
                q.push(next_pos);
            }
        }
        if (dist[pos + 1] >= dist[pos] + 1) {
            dist[pos + 1] = dist[pos] + 1;
            q.push(pos + 1);
        }
    }
    
    cout << dist[D] << '\n';
    
}

 

다이나믹 프로그래밍은 점화식을 다익스트라를 변형한다.

이미 이전 위치에 놓인 거리는 계산이 완료됐다는 가정을 두면 떠올리기 쉽다.

- dist[i]: 길 i로 가는 최소 비용

💥 만약 dist[i]로 가는 지름길이 없을 때: dist[i] = dist[i - 1] + 1

💥 만약 dist[i]로 가는 지름길이 있을 때:

dist[i] = min(dist[i - 1] + 1, dist[start] + cost)(start: 지름길의 시작점, cost: 지름길의 길이)

이를 위해서는 지름길을 기록할 때 to, 즉 지름길의 끝점을 기준으로 삽입하면 고효율로 지름길을 탐색할 수 있다.

 

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
vector<vector<pair<int,int>>> shortcut(10000);
vector<int> dist(10000, 10000);
priority_queue<int> q;

int main() {
    int N, D;
    cin >> N >> D;
    for(int i = 0;i < N;i++) {
        int a, b, d;
        cin >> a >> b >> d;
        shortcut[b].push_back({a, d});
    }
    dist[0] = 0;
    for(int i = 1;i <= D;i++) {
        dist[i] = dist[i - 1] + 1;
        for(int j = 0;j < shortcut[i].size();j++) {
            int from = shortcut[i][j].first;
            int cost = shortcut[i][j].second;
            
            dist[i] = min(dist[i], dist[from] + cost);
        }
    }
    
    cout << dist[D] << '\n';
}

아무래도 다이나믹 프로그래밍을 지나치게 못 푸는 거 같다...ㅠ

아무리 생각해도 혼자만의 힘으로는 잘 떠오르지가 않는다.

문제를 더 많이 풀어야지.