[ 백준 15971 ] 두 로봇 (c/c++)

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

 

 

[ 문제 요약 ]

두 로봇이 서로 통신을 하기 위해서는 동굴 내의 같은 통로 위에 위치해야만 한다. 임의의 통로의 양 끝에 위치한 두 방들도 그 통로 위에 위치해 있다고 간주할 때, 두 로봇이 주어질 때 두 로봇이 통신하기 위해서 이동해야 할 최솟값을 출력한다.

 

 

[ 문제 풀이 ]

1. 두 로봇이 이동해야 될 최솟값은 두 로봇 사이의 최소 거리에서 가장 긴 통로의 길이를 빼면 된다.

2. 한 로봇에서 이동해서 DFS를 통해 검사하면서 두 로봇 사이의 거리와 가장 긴 통로의 길이를 갱신한다.

3. 만약 한 로봇이 다른 로봇의 위치에 도달한다면 이동할 최솟값을 출력한다.

 

 

[ 소스 코드 ]

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

int N, R1, R2;
int visited[101010];
vector<pair<int, int>> v[101010];

void DFS(int n, int sum, int max_dist){
    visited[n] = 1;
    if (n == R2){
        cout << sum - max_dist;
        return;
    }
    
    for (int i=0; i<v[n].size(); i++){
        if (!visited[v[n][i].first]){
            visited[v[n][i].first] = 1;
            DFS(v[n][i].first, sum + v[n][i].second, max(max_dist, v[n][i].second));
        }
    }
    return;
}

int main() {
    cin >> N >> R1 >> R2;
    for (int i=0; i<N-1; i++){
        int a, b, val;
        cin >> a >> b >> val;
        v[a].push_back(make_pair(b, val));
        v[b].push_back(make_pair(a, val));
    }
    DFS(R1, 0, 0);
    
    return 0;
}

 

 

[ 주의할 점 ]

두 로봇이 짧은 거리를 서로 이동하는 것이 아니라 두 로봇 사이의 최소 거리에서 가장 긴 통로의 길이를 빼는 것이라는 문제 풀이법을 생각해야 했다.