[BOJ C++] 백준 15971번: 두 로봇

 📚 문제

[BOJ C++] 백준 15971번: 두 로봇
https://www.acmicpc.net/problem/15971

 

---

 📝 입력 및 출력

 

---

 🔎 문제 풀이

•  두 점이 주어졌을 때, 최소 비용으로 갈 수 있는 경로를 찾으면 반 이상 해결되는 문제이다. 각 통로에 길이가 없는 문제였다면 BFS로 해결하는 것이 훨씬 효율적이겠지만, 이번 문제에는 통로마다 길이가 주어져 있기 때문에 가장 적은 노드를 지나는 것이 꼭 최소비용이 되는 것은 아닐 것이라 생각하여 스택을 사용한 DFS로 구현해보았다.
•  두 로봇은 하나의 통로에서 만나서 서로 통신한다. 또, 두 로봇이 서로 통신하기 위해 이동해야 하는 거리의 합의 최솟값을 찾아내야하므로, 두 노드를 연결하는 통로들 중, 가장 긴 통로에서 만난다면 로봇들의 이동거리 합은 최소가 된다.
•  예를 들어, 두 노드를 연결하기 위해 지나가야 하는 통로의 길이가 <8 - 10 - 14 - 7>라면 두 노드를 연결하는 비용은 총 39이고, 통로의 길이가 14인 통로에서 만날 때 로봇들의 이동거리 합이 25로 최소가 된다. 즉, 로봇들의 이동거리 합은 두 노드를 연결하는 최소 비용 - 이동 경로 중 가장 긴 통로의 길이로 구할 수 있다.

 

 ✅ 오류 1

 처음에는 위 사진과 같은 경우가 발생할 수도 있지 않을까? 라고 생각했다. 1에서 6으로 이동한다고 할 때의 비용은 <1 - 2 - 5 - 6> 일 때 32, <1 - 2 - 5 - 9 - 6> 일 때 25이므로 두 번째 경로를 선택한 경우가 최소이기 때문이다. 그러나 문제에서 "임의의 두 방 사이를 이동할 때 같은 통로를 두 번 이상 지나지 않는 경로는 유일한 것으로 밝혀졌다." 라고 했으므로 두 노드를 잇는 경로는 여러 개 나올 수 없다. 즉, 위와 같은 경우를 고려할 필요가 없다는 것이다. (제발 문제를 잘 읽자 ....)

 

 ✅ 오류 2

 두 노드 사이의 길이를 저장할 때 인접 행렬 방식으로 저장하였다. 그러나 이런 방식으로 저장한다면 N의 최댓값이 100,000까지 올라가므로 100,000 * 100,000인 어마어마한 크기의 2차원 행렬이 필요하다. 이때의 공간 복잡도는 $O(N^2)$이므로 $(100,000)^2 = 10,000,000,000$이고, 약 40GB의 메모리가 필요하다. 따라서 시간 초과가 발생할 수 밖에 없다. 따라서 인접 행렬이 아닌 인접 리스트의 형식으로 두 노드 사이의 길이를 저장해야 한다.

 

 

 인접 리스트란, v[i]에 i번 노드와 연결된 노드의 정보만을 저장하는 방식을 말한다. 이번 문제에서는 노드 간 길이도 알아야 하므로 <연결된 노드의 번호, 길이>를 쌍으로 연결하여 저장하였다. 위 그림을 예시로 들자면, 2번 노드에 연결된 노드는 1번, 3번, 4번, 5번이 있다. 따라서 v[2]에 {1, 8}, {3, 6}, {4, 5}, {5, 10}을 저장한다. 저장 결과는 다음 표와 같이 나타난다.

i	v[2][i].first	v[2][i].second
[0]	1	8
[1]	3	6
[2]	4	5
[3]	5	10

 

---

 ⌨️ C++ 코드

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

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

    int n, b, e;
    cin >> n >> b >> e;
    vector<vector<pair<int, int>>> v(n + 1);
    vector<int> dis(n + 1); // 현재 노드까지의 최소 비용.
    vector<int> maxpass(n + 1); // 경로 중 가장 긴 통로의 길이.

    for (int i = 0; i < n - 1; i++) { // 인접 노드 간 정보 저장.
        int p, q, l;
        cin >> p >> q >> l;
        v[p].push_back(make_pair(q, l));
        v[q].push_back(make_pair(p, l));
    }
    for (int i = 1; i <= n; i++) dis[i] = MAX; // 아직 방문하지 않은 노드까지의 거리를 최댓값으로 설정.

    stack<int> s;
    s.push(b);
    dis[b] = 0;
    maxpass[b] = 0;
    while (!s.empty()) {
        int cur = s.top();
        for (int i = 0; i < v[cur].size(); i++) {
            int next = v[cur][i].first;
            if (dis[next] == MAX) { // 방문하지 않은 경우.
                s.push(next);
                dis[next] = dis[cur] + v[cur][i].second;
                maxpass[next] = max(maxpass[cur], v[cur][i].second);
            }
        }
        if (cur == s.top()) s.pop();  // 더 이상 나아갈 곳이 없는 경우.
    }
    cout << dis[e] - maxpass[e];
}