두 로봇(BOJ15971)

문제

이미지 클릭

문제 설명

• 모든 동굴은 통로로 연결되어 있다.
• 이때 로봇은 인접한 동굴에 위치하게 된다면 통신이 가능하게 된다.
• 동굴사이를 이동하기 위해서는 특정 길이의 통로를 통과해야 한다.
• 최소한의 길이로 이동하도록 코드를 작성하시오.

문제 해설

• bfs

기본적으로 A동굴에서 B동굴로 이동하는 경로는 한 가지밖에 존재하지 않는다.
또한 A-B로 이동하는 경로 어디에서든지 만나도 상관이 없다.

ex) 1-3-5-7의 경로가 있다고 할 때 동굴 1,3에서 만나도 상관없고, 3,5에서 만나도 상관없음.

즉 경로를 이동하면서 통로의 길이를 모두 더해준 다음, 제일 긴 경로를 빼주면 된다.

최종 코드

#include <bits/stdc++.h>
using namespace std;
struct P {int a, sum, mx;};
int n, a, b;
int visited[100004];
vector<pair<int, int>> v[100004];
int main() {
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> a >> b;
    for (int i = 1; i <= n; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        v[x].push_back({y, z});
        v[y].push_back({x, z});
    }
    queue<P> q;
    q.push({a, 0, 0}); 
    visited[a] = 1;
    while (!q.empty()) {
        int x = q.front().a;  #로봇의 현제 위치  
        int sum = q.front().sum; #지금 까지 이동하면서 통과한 통로 길이의 총합
        int mx = q.front().mx;  #지금 까지 이동한 통로중 가장 긴 통로의 길이
        q.pop();
        if (x == b) { #도착하면 총합-제일 긴 통로!
            cout << sum - mx; 
            return 0;
        }
        for (auto [y, d] : v[x]) {
            if (!visited[y]) {
                visited[y] = 1;
                q.push({y, sum + d, max(mx, d)}); #일반적인 bfs 탐색(?)
            }
        }
    }
}

이미지 클릭