c++ 백준_1167_"트리의 지름"

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

1167번: 트리의 지름

 

정점이 100,000 개라서

무조건 n² 이 되게 하면 안될 거 같았다.

​

그래도 하지말라는 거 괜히 해보기 ㅎ

leaf 노드를 시작으로 다 DFS를 돌려보니 역시

시간초과

ㅎ

​

​

​

그래서 kruskal 이니,

노드의 가중치를 이전 노드에서 더해서 어쩌구,

가지치기 처럼 해보니 마니

하면서

​

혼자 예제를 만들었는데

​

정점이 6개인 트리이다.

​

이 트리를 보며

1 에서 dfs를 시작해서 (1 - 2)의 가중치를 어떻게 저장하며

(2 - 1 - 6 - 5 ) = 15 의 가중치를 어떻게 만들지 고민했다.

​

1 에서 DFS를 시작해 가장 거리가 먼 노드(5) 에 도착 후,

다시 5에서 DFS 를 시작하면 (2) 에 도달해 15 반환이 되었다.

​

이런 얼렁뚱땅 방법이 되길래 코드를 작성해보고

던지는 식으로 다시 제출했는데

​

띠링?

​

기분은 좋았지만 찝찝함..

급똥 해결 후 쾌락 but 덜 닦은 느낌

​

​

​

구글에 트리 지름 구하는 공식을 검색해봤다.

​

jooon na 감동이여야할지,

이게?

라고 반응해야할지

​

트리의 지름 구하는 공식 중 하나는 정확히 이런 방법이였다 !

​

​

​

왜인가 싶어 설명을 보니

하나 같이 이해를 못하겠다 !

​

​

​

그래서 혼자 나름 내 코드과 왜 답이 되는지 이해를 해보았다.

​

트리라는 점을 먼저 인지하고,

(트리의 성질)

​

노드의 한 점에서 DFS를 시작해 가장 먼 노드로 이동하였다.

그럼 트리이니 root 노드가 존재하기 때문에

1을 root라 가정하고 오른팔에서 가장 큰 거리를 가져온 격이 된다.

그럼 1의 왼쪽도 봐야한다.

​

이미 1의 오른쪽에서 가장 큰 거리(가중치)를 구했으니 그 마지막 노드(5) 에서

시작하면 1을 통해 자연스레 왼팔로 스근하고 부드럽게 넘어가

트리를 쭉 펼쳤을 때의 가장 큰 지름이 되지

아니 한가

하는

작고 귀여운 나만의 생각.

​

​

위의 경우에는 루트가 이진 트리지만

루트(1)에서 가지가 많아도 먼저 가장 먼 거리를 골랐기 때문에

두번째, 다시 가장 먼 노드에서 DFS할 때는

거기서 이미 구한 첫번째 DFS + 한 곳 방향으로 밖에 가지 못한다.

(지름이기 때문에)

or

첫번째 DFS에서 구한 길이 있을 것이다.

그럼 이미 그 방면은 다 체크한게 된다.

그래서 다시 두번째 DFS를 진행할 때

루트 (1)을 지나지 않고

가장 먼 거리를 만들 수 있는 가중치가 있다면

그쪽으로 확인하면 된다.

​

​

​

가슴으로는 와닿는데 표현이 안되네...☆

​

​

새벽에 억지로 이해안되는 거 이해하려니

내가 뭔 소리하는지 모르겠다

이래서 설명을 할 수 있을 레벨이 되어야 된다.

​

​

코드는 간단한데 심오하구만

 

 

#include <iostream>
#include <vector>
using namespace std;

vector<vector<pair<int, int>>> node(100001);
vector<bool> visit(100001, false);

int longest = 0;
int last = 0;

void dfs(int u, int weight) {

	visit[u] = true;

	if (weight > longest) {
		longest = weight;
		last = u;
	}

	for (int i = 0; i < node[u].size(); i++) {
		if (visit[node[u][i].first])
			continue;

		dfs(node[u][i].first, weight + node[u][i].second);
	}
}

int main(void) {

	int V;
	cin >> V;


	int u, v, weight;

	for (int i = 0; i < V; i++) {

		cin >> u;

		while (1) {
			cin >> v;
			if (v == -1)
				break;
			cin >> weight;

			node[u].push_back(make_pair(v, weight));
		}
	}

	dfs(1, 0);

	for (int i = 1; i <= V; i++) {
		visit[i] = false;
	}
	dfs(last, 0);

	cout << longest;

}