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

 📚 문제

[BOJ C++] 백준 1916번: 최소비용 구하기
https://www.acmicpc.net/problem/1916

 

 

---

 📝 입력 및 출력

 

---

 🔎 문제 풀이

 구현 과정

이 문제는 앞서 공부했던 이론인 다익스트라 알고리즘을 활용하여 해결할 수 있다.

[이론] 다익스트라 알고리즘

• 다익스트라 알고리즘이란? 하나의 정점에서 출발하여 그래프 상의 다른 모든 정점까지의 최단 경로를 찾는 알고리즘이다.
• 주의해야 할 점은 노드에서 노드로 가는 간선이 유일하지 않다는 점이다. 즉, A 도시에서 B 도시로 가는 버스가 여러 개 존재할 수 있다.

자세한 구현 방법은 다음과 같다.

 

• 먼저 버스의 정보를 모두 받아 2차원 벡터(v)에 저장한다. 두 도시를 연결하는 버스 정보가 없는 길은 무한으로 나타내야 하므로 초기값을 모두 INF으로 저장한다. INF 값은 도시의 개수(1,000) * 버스 비용 (100,000)인 100,000,000 이상으로 설정해야 한다. 그 이유는 아래 그림과 같다.

 

• v[s][e]는 s 도시에서 e 도시로 가는 버스 비용을 의미한다. 이때, s 도시에서 e 도시로 가는 버스가 여러 대 있을 수 있으므로 이미 저장되어 있는 값과 새로 입력받은 값 중 더 작은 값을 골라 저장한다.
• 버스 정보를 모두 저장했다면 출발 도시부터 도착 도시까지의 최소 비용을 구해야 한다. 다음으로 선택한 도시를 cur라고 하고, 출발 도시부터 다른 도시까지의 거리는 dis 배열에 저장한다. 또, 이미 비용이 최소인 도시는 그보다 더 적은 비용으로 갈 수 없으므로 방문 여부를 visited 배열에 저장한다. (음수 가중치가 없으므로 비용을 다시 감소할 수는 없음.) 출발 도시부터 출발 도시까지의 거리는 0이므로 dis[start]=0으로 설정한다.

이후부터는 아래 과정을 반복한다. (방문 처리 - 거리 갱신 - 노드 선택)

• 현재 도시를 선택한 것이므로 visited[cur]=true로 설정하고, cur 도시와 연결된 도시들 중 아직 방문하지 않은 도시의 dis 값을 갱신한다. 기존에 저장된 값과 cur을 거쳐 방문했을 때의 값 중 더 작은 값을 골라 저장한다.
• 다음으로 방문할 도시를 선택하기 위해 거리가 최소인 도시를 찾아 cur로 설정한다.

 

 예시 풀이

예제 1을 풀어보도록 하자. 도시는 5개, 버스는 8개가 존재한다. 1번 도시에서 5번 도시까지 가는 최소 비용을 찾아야 하고, 버스 정보를 그림으로 나타내면 다음과 같다.

dis 배열의 초기값은 INF(100,000)로 설정한다.

1번 도시에서 출발하므로 처음 방문하는 도시는 1번 도시이다. visied[1]=true로 변경하고, 1번 도시에 연결된 도시들의 거리를 갱신한다. 1번 도시에서 1번 도시로 가는 비용은 0이다.

아직 방문하지 않은 도시들 중 가장 비용이 작은 도시를 선택하여 visited 값을 true로 변경한다. 4번 도시의 비용이 1로 가장 작으므로 visited[4]=true로 변경하였다. 그 후, 4번 도시를 거쳐간 경우의 비용이 더 적은 경우가 있다면 dis 값을 갱신한다. dis[5]의 기존 값은 10인데, 1번-4번-5번으로 이동하는 경우에는 1+3=4의 비용이 든다. 1번 도시에서 5번 도시로 바로 이동하는 것보다 4번 도시를 거쳐 이동하는 것의 비용이 더 적으므로 값을 갱신한다.

다음으로 가장 적은 비용이 드는 도시인 2번 도시를 선택하고, 이웃한 도시인 4번 도시를 확인한다.

그러나 4번 도시는 이미 방문한 도시이므로 거리를 갱신할 필요가 없다. (이미 최솟값이기 때문.)

다음 도시는 3번 도시이다. 이웃 도시는 4번, 5번 도시인데, 4번 도시는 이미 방문했으므로 확인하지 않는다.

5번 도시의 기존값과 3번 도시를 거쳤을 때의 값이 동일하므로 갱신하지 않는다.

다음 도시는 5번 도시이다. 5번 도시는 이웃한 도시가 없으므로 확인할 필요가 없다.

다익스트라 알고리즘이 완료되었다. 시작 도시(1번)부터의 각 도시까지의 거리를 모두 계산했으므로, 도착 도시까지의 거리를 출력하기만 하면 된다.

 

 반례 찾기 Tip

• https://testcase.ac/problems/1916
• 질문 게시판에 여러 반례가 올라와있지만, 이 사이트를 통해 확인해 보는 것을 추천한다. 여러 반례를 한 번에 확인해 줘서 틀린 부분을 쉽게 찾아낼 수 있다! 필자도 틀렸습니다를 한 번 받았었는데 testcase.ac에 돌려본 결과 무한대 값이 너무 작아서 문제가 발생한 것을 발견할 수 있었다. (사실 질문 게시판을 꼼꼼히 읽지 않아서 몰랐던 것 ...)

 

---

 ⌨️ C++ 코드

#include <bits/stdc++.h>
using namespace std;

int main(void) {
    cin.tie(NULL);
    ios::sync_with_stdio(false);

    int n, m, start, end, INF = 100000000;
    cin >> n >> m;
    vector<vector<int>> v(n + 1, vector<int>(n + 1, INF));
    vector<bool> visited(n + 1);
    vector<int> dis(n + 1, INF);
    for (int i = 0; i < m; i++) {
        int s, e, cost;
        cin >> s >> e >> cost;
        v[s][e] = min(v[s][e], cost);
    }
    cin >> start >> end;
    dis[start] = 0;
    int cur = start;
    for (int i = 1; i <= n; i++) {
        visited[cur] = true;
        for (int j = 1; j <= n; j++)
            if (visited[j] == false) dis[j] = min(dis[j], dis[cur] + v[cur][j]);

        int min_val = INF;
        for (int j = 1; j <= n; j++) {
            if (visited[j] == false && dis[j] < min_val) {
                min_val = dis[j];
                cur = j;
            }
        }
    }
    cout << dis[end];
}