c++ 1595번 북쪽나라의 도로 (백준)

#include <cstdio>
#include <vector>
#define MAX 10001

using namespace std;

vector<pair<int, int> > vec[MAX];
vector<bool> v;
int ans, index; //ans : 트리에서 가장 긴 간선들의 합, index : 처음 DFS을 돌려서, 임의의 점 중 가장 먼 곳에 있는 점의 인덱스

void DFS(int root, int dis) {
	v[root] = true;
	
	if(dis > ans) { //이전의 가장 긴 거리보다 더 크다면, ans와 index을 갱신한다.
		ans = dis;
		index = root;
	}
	
	for(pair<int, int>x : vec[root]) { //연결된 간선들 중
		if(!v[x.first]) { //방문하지 않은 것만
			DFS(x.first, x.second + dis);
		}
	}
}

int main(void)
{
	int a, b, c;
	while(~scanf("%d %d %d", &a, &b, &c)) {
		vec[a].push_back({b, c});
		vec[b].push_back({a, c});
	}

	v.assign(MAX, false); //방문벡터 초기화
	DFS(a, 0); //임의의 점을 시작점으로 DFS 시작 -> 임의의 점에서 가장 먼 점의 인덱스를 얻음
	v.assign(MAX, false); //방문벡터 초기화
	DFS(index, 0); //index는 트리에서 가장 바깥에 있기 때문에, dfs을 돌리면 가장 먼 곳과의 거리가 나오게 됨

	printf("%d", ans);
}

 

풀이 : DFS 두번 (한 번은 최대 길이를 이루는데 속한 경로에서 가장 끝에 있는 정점 중 하나의 인덱스를 구함

                            다음 한 번은 최대길이를 구함)

 

트리에서 가장 긴 거리를 구해야 합니다. 그러나 어디에서 시작해야할 지를 잘 모릅니다.

그렇다고 모든 점에서 DFS을 돌리기엔 시간이 너무나도 부족합니다.

그러나  DFS을 두번만 돌리면 간단히 구할 수 있습니다.

 

시작할 위치를 구하기 위해서도 DFS을 합니다.

 

임의의 점에서 DFS을 돌리고 이 과정에서 최장 거리와 (ans), 최장거리일 때 도달한 점의 index을 따로 저장합니다.

 

여기서 ans는 임의의 트리에서 가장 긴 거리일 가능성도 있습니다.

 

여기서 index는 임의의 트리에서 가장 긴 거리를 이루는 두 점 중 하나가 됩니다.

 

어떤 점을 잡던 간에 DFS을 돌리게 되면

거리의 최댓값을 얻을 때 위치한 점은 양 끝에 있는 index 2 또는 index 4 입니다.

 

 

7-3-1-9-8 이 최대 길이를 만드는 경로이다.

 

여기서 모든 임의의 점에서 DFS을 돌리게 되면 8  이나 7에 도달하게 된다.

 

여기서 8 이나 7로 DFS을 돌리면 위 트리에서 거리의 최댓값을 구할 수 있게 된다.

 

https://csacademy.com/app/graph_editor/

CS Academy

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

1595번: 북쪽나라의 도로