(C++) - 백준(BOJ) 1446번 : 지름길

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

1446번: 지름길

brute force로 풀었습니다.

 

 

풀이방법

 1. 인접리스트로 지름길의 출발점, 도착점 그리고 길이정보들을 간선과 해당 비용으로 생각해 저장합니다. 저장할 때 주의할 점이 두 가지 있습니다. 도착점 - 출발점 사이의 거리가 길이정보 이하라면 사실상 지름길이 아니므로 볼 필요가 없습니다. 배보다 배꼽이 더 큰 상황이죠 두 번째로는 예시에 나와있듯이 도착지점이 d를 넘어가는 경우에도 간선정보를 만들 필요가 없습니다.

 

 2. dist배열에 i에 도착하기 위한 최소 운전 길이를 저장합니다. 지름길을 탔을 때와 이전 경로에서 그냥 운전했을 때를 비교해 최솟값을 dist[i]에 저장합니다.

 

 3. 답 출력 : dist[d]를 출력합니다.

 

Code

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
using pii = pair<int,int>;
int n, d, dist[10001], ans;
struct Edge { int v, w; };
vector <Edge> graph[10001];

int main(){
    memset(dist,INF,sizeof(dist));
    cin >> n >> d;
    dist[d] = d;
    
    for(int i = 0; i < n; i++){
        int u,v,w;
        cin >> u >> v >> w;
        if(v - u <= w) continue; //지름길이 아닌경우
        if(v > d) continue; //도착지점이 d 넘어가는 경우
        graph[u].push_back({v,w});
    }

    int prev = -1;    
    for(int i = 0; i <= d; i++){

        if(i) prev = dist[i-1];
        dist[i] = min(dist[i], prev + 1);

        for(auto next : graph[i]){
            if(dist[next.v] > dist[i] + next.w) 
                dist[next.v] = dist[i] + next.w;
        }
    }

    cout << dist[d];
}