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

1.문제설명

두 로봇이 통신하기 위해 이동해야하는 최단 거리를 구해야한다.

두 로봇은 같은 노드에 있거나 서로 연결된 노드에 위치하면 통신할 수 있다.

2.접근방법[알고리즘]

처음에는 문제에 주어진 대로 로봇 두대를 놓고 한 로봇 씩 이동시키면서 

통신할 수 있는지 확인하고 그 때 이동한 거리를 계속 갱신해주면서 답을 구했는데

이러면 n이 10만이기 때문에 시간초과로 틀렸다.

문제의 조건에서

N개의 노드와 N-1의 간선이 있기 때문에

이미 지나온 노드를 재방문 할 수 없을 때

출발 지점에서 도착 지점까지 가는 경로는 무조건 하나만 나오고, 그게 최단 경로가 된다.

이 문제를 해결하려면

1. 두 로봇의 시작점 사이의 거리를 구한다.

2. 시작점을 이어주는 통로 중 길이가 가장 긴 간선을 구한다.

3. 답 = 시작점 사이 거리 - 가장 긴 간선 거리 

3.문제풀이코드 C++

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

int n, s1, s2;
vector<pair<int, int> > m[100001];

bool ch[100001];
bool flag = false;

void DFS(int x, int sum, int max_dist) {
	if (flag) return;
	if (x == s2) {
		cout << sum - max_dist << '\n';
		flag = true;
		return;
	}

	for (int i = 0; i < m[x].size(); i++) {
		int nx = m[x][i].first;
		int nd = m[x][i].second;
		if (ch[nx] == 0) {
			ch[nx] = 1;
			DFS(nx, sum + nd, max(nd,max_dist));
		}
	}

	return;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> s1 >> s2;
	for (int i = 0; i < n - 1; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		m[a].push_back({ b,c });
		m[b].push_back({ a,c });
	}
	ch[s1] = 1;
	DFS(s1, 0, 0);

	return 0;
}

DFS를 돌면서 다른 로봇의 시작점을 만나면 바로 종료해주면 된다.

해당 정점까지 가는 다른 방법이 존재하지 않기 때문이다.