[백준 / BOJ] C++ 15971 두 로봇

15971번: 두 로봇

 

문제

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

15971번: 두 로봇

 

 

풀이

동굴에서 두 점 A, B에서 각자 최소한으로 움직여 간선 하나를 남겨두고 마주할 수 있을 때 통신이 가능하다. 이때 최단 이동 거리를 구하는 문제다. 처음엔 bfs로 A에서 B까지 도달한 다음 B에서 다시 bfs를 시작해 최단 경로 위에서 B의 이동 거리와 B가 이제 갈 곳까지의 A의 이동 거리의 합이 최소인 것을 찾아줬으나 틀렸습니다를 받았다.

 

친구에게 힌트를 얻었고 시도해 봤다. dfs로 (현재 위치, 지금까지 거리, 지나온 거리 중 최장 간선)을 파라미터로 받아준다. A에서 시작해 현재 정점에서 간선을 지나 다음 정점으로 나아가며 탐색을 해주고 B에 도달하게 되면 그때까지 A->B 최단 거리에서 지나온 간선 중 가장 긴 간선의 길이만큼 빼주면 최단 경로가 된다.

 

 

코드

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

int N, A, B;
vector<pair<int, int>> graph[100001];
vector<int> visited(100001, 0);

void dfs(int curr, int dist, int d) {
  if (curr == B) {
    cout << dist - d << '\n';
    return;
  }
  visited[curr] = 1;
  for (auto i : graph[curr]) {
    int next = i.first;
    int cost = i.second;
    if (!visited[next])
      dfs(next, dist + cost, max(d, cost));
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> N >> A >> B;
  for (int i = 1; i < N; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    graph[a].push_back({b, c});
    graph[b].push_back({a, c});
  }
  dfs(A, 0, 0);
  return 0;
}