[C++] 백준 1916번: 최소비용 구하기

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

---

문제 이해하기

 문제의 요구사항은 다음과 같습니다.

출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 구하여라.

---

시간복잡도 어림하기

다익스트라(데이크스트라) 알고리즘

 한 노드에서 다른 한 노드까지의 최단거리를 구하는 문제이므로 다익스트라 알고리즘을 사용할 수 있습니다. 다익스트라 알고리즘의 시간복잡도는 O(ElogV)입니다. 문제에서 E(간선의 수)는 최대 100,000이고, V(노드의 수)는 최대 1000입니다. 100000 x log(1000)은 백만보다 작은 수이므로 제한 시간내에 문제를 해결하기 충분합니다.

---

알고리즘 설계하기

 다익스트라 알고리즘은 다음과 같은 순서로 동작합니다.

1. 시작 노드와 인접한 노드들의 최단거리를 갱신하고 시작 노드를 방문 처리한다.
2. n - 1번 아래 동작을 반복한다.
 2-1. 현재 최단거리 배열에서 방문하지 않은 노드 중, 가장 가까운(배열 값이 가장 작은) 노드를 선택한다.
 2-2. 선택한 노드를 방문 처리하고, 선택한 노드와 인접한 노드들의 최단거리를 갱신한다.
 2-3. 2-1로 돌아간다.

 

 여기서 가장 핵심이 되는 부분은 최단거리 배열 값이 가장 작은 노드를 선택하는 부분과 선택한 노드에 대해 인접한 노드들의 최단거리를 갱신하는 부분입니다.

 

 먼저, 최소 거리값을 가지는 노드를 찾는 부분입니다. 현재 방문하지 않은 배열에 대해 최단거리 값을 찾는 알고리즘을 설계하면 됩니다.

 단순하게 생각하면 for루프로 모든 노드를 탐색하면서 방문하지 않은 노드 중, 현재 최솟값보다 작은 거리를 가진 노드가 있다면 최단거리를 갱신하고 현재 노드를 반환 값으로 초기화하여 구할 수 있습니다. 또한, 현재 최단 거리 중 가장 작은 값을 가지는 노드만 찾으면 되므로 우선순위 큐를 사용할 수도 있습니다.

 

 선택한 노드에 대해 인접한 노드들의 최단거리를 어떻게 구할 수 있을까요? 선택한 노드에 대해 인접한 노드를 방문한다는 것은 시작 노드에서 다음 노드로 이동할 때, 선택 노드를 경유한다는 의미입니다. 따라서 다음 노드 i에 대해 현재 i까지의 최단거리와 선택 노드까지의 최단거리 + 선택 노드와 i노드 까지의 가중치를 비교하면 됩니다. 코드로는 다음과 같이 나타낼 수 있습니다.

dist[i] = dist[선택노드] + adj[선택노드][i];

 

---

알고리즘 구현하기

 최종 코드는 다음과 같습니다.

#include<iostream>
#include<vector>
#define INF 1e9
using namespace std;

int n, m, dist[1004], visited[1004], adj[1004][1004];
int getNextNode(){ //최소 거리값을 갖는 노드를 찾음
    int mn = INF;
    int idx = 1;
    for(int i = 1; i <= n; i++){
        if(visited[i]) continue;
        if(dist[i] < mn){
            mn = dist[i];
            idx = i;
        }
    }
    return idx;
}

int main() {
	/*모든 최단거리 무한대로 초기화*/
    fill(&adj[0][0], &adj[0][0] + 1004 * 1004, INF);
    /*입출력 성능 향상*/
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m;

    int st, ed, w;
    for(int i = 0; i < m; i++){
        cin >> st >> ed >> w;
        adj[st][ed] = min(adj[st][ed], w); //같은 출발지점과 도착지점을 가지는 간선이 여러개일 수 있음
    }
    cin >> st >> ed;
    for(int i = 1; i <= n; i++) dist[i] = adj[st][i]; //시작 지점과 연결된 노드까지의 최단거리
    dist[st] = 0; visited[st] = 1;

    for(int i = 0; i < n - 1; i++){
        int cur = getNextNode();
        visited[cur] = 1;
        for(int j = 1; j <= n; j++){ //방문하지 않은 노드에 대해 최단거리 갱신
            if(visited[j]) continue;
            dist[j] = min(dist[j], dist[cur] + adj[cur][j]);
        }
    }
    cout << dist[ed];
    return 0;
}

 가장 먼저 인접 행렬을 INF로 초기화 해주고 간선을 입력 받았습니다. 이때, 같은 출발지점과 도착지점을 가지는 간선이 존재할 수 있으므로 이들 중 가장 작은 가중치를 갖는 간선으로 인접 행렬을 구성합니다.

 

 이후 시작 노드에 대해 최단 거리 값을 초기화하고, for 루프를 n - 1번 반복하며 시작 노드에 대해 각 노드까지의 최단거리를 계산합니다.

---