[백준 1916] 최소비용 구하기 (C++)

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

다익스트라

도시를 연결하는 단방향 버스 (출발점, 도착점, 비용)이 주어지고

임의의 출발점과 도착점이 주어졌을 때, 이 둘을 잇는 최소 비용을 출력하는 문제

 

접근방법 

음수인 비용이 없어서 다익스트라로 풀어도 된다. (벨만포드로 안풀어도 됨)

이거 풀다가 내가 다익스트라를 제대로 이해하고 있는게 맞나 의심했음..다시 공부해야 할 것 같다..

다익스트라 기본 개념은 임의의 출발점 하나에 대해 모든 노드에 대한 최소 거리를 저장하고 있는 1차원 배열이 하나 있고,

방문한 노드를 하나씩 추가해 가면서 이 배열을 갱신하는 방식이다.

 

이 문제를 풀 때는,

- 인접행렬 (각 노드에 대해 연결된 버스 노선을 담고 있는 2차원 배열. ex. 1번: {(2번도시, 비용2), (3번도시, 비용3), (4번도시, 비용4),,,} 이런식이다.)

- 출발점으로부터 각 노드의 최소거리를 저장하게 될 1차원 배열 (distance[])

- 노드의 방문여부를 저장한 1차원 배열 (visit[])

- 방문한 노드의 갯수 (visitedNode)

 

반복문을 돌면서 distance를 계속 갱신해줬는데, 이 반복문은 모든 노드를 방문할 때 까지만 반복한다.

그 안에서는 매번 distance가 최소이면서 아직 방문하지 않은 노드를 하나 선택해서, 그 노드(cur)에 방문한다.

그 노드에 방문한다는 건, 그 노드에서 출발해서 갈 수 있는 버스를 탈 수 있다는 것과 같다.

따라서 cur에 연결된 버스를 인접행렬(adj)를 참고하여 모두 순회한다.

하나의 버스를 볼 때 마다, 그 버스의 도착점(next)에 대한 최소비용을 갱신한다.

따라서, 현재 가장 가까운 노드 하나를 추가하는데, 이때 그 노드와 직접적으로 연결되는 노드의 최소비용만 갱신하는 것

 

일단 이 문제는 이렇게만 풀어도 통과가 됐는데, 다익스트라 풀이하는 다른 풀이들을 봐보니 간선하나에 대한 도착노드만 보는 것 같지가 않아서 다시 공부해봐야겠다고 느꼈음. 

 

오답노트

첨에 양방향인줄..단방향이었다..그리고 가장 가까운 노드를 찾을 때 min 값으로 22222로 대충 설정해뒀더니 안됐다.

987654321이걸로 고쳤더니 됐음. 아우 너무 헷갈려!!

 

소스코드

#include <iostream>
#include <vector>

using namespace std;
int INF = 987654321;

int main(){
    
    // input
    int N, M;
    cin >> N >> M;
    
    vector<vector<pair<int, int>>> adj(N+1);
    int s, e, c;
    for(int i = 1; i <= M ; i++){
        cin >> s >> e >> c;
        adj[s].push_back(make_pair(e, c)); // 단방향이었음!
    }
    
    vector<int> distance(N+1, INF);
    
    int S, E;
    cin >> S >> E;
    
    distance[S] = 0;
    
    // process
    vector<bool> visit(N+1, false);
    int visitedNode = 1;
    
    while(visitedNode < N){
        int cur = 1;
        // 방문하지 않은 노드 중 가장 가까운 노드 선정
        int min = INF;
        for(int i = 1; i <= N ; i++){
            if(!visit[i] && min >= distance[i]){
                min = distance[i];
                cur = i;
            }
        }
        visit[cur] = true;
        visitedNode++;
        
        for(int i = 0; i < adj[cur].size() ; i++){
            int next = adj[cur][i].first;
            int next_cost = adj[cur][i].second;
            // 간선 사용하여 거리 갱신
            if(distance[next] > distance[cur] + next_cost){
                distance[next] = distance[cur] + next_cost;
            }
        }
    }
    
    cout << distance[E];
    
}