[백준 1967] C++ 트리의 지름

1. 문제

---

2. 분석

---

맨 처음엔 루트에서 가장 먼 두 점을 구해서,

그 두 점에서 부터 역으로 부모 노드 쪽으로 올라가다 같은 부모 노드를 보고 있게 되면

(가장 먼 두 점까지의 거리의 합) - (2 * 부모 노드까지의 거리의 합) 의 형태로 구하려 했으나 실패.

 

하지만, 루트에서 가장 먼 한 점은 결국 이 트리의 지름의 한 점이 된다는 것은 확실하다.

그리고 그 점에서 다시 가장 먼 한 점을 구하면, 지름의 나머지 한 점을 구할 수 있게 된다!

 

이 아이디어만 가지면 쉽게 구할 수 있었을 텐데, 생각이 나질 않았다.

 

*해당 아이디어는 아래 블로그에서 채용했다.

https://codingwell.tistory.com/61

[ 백준 ] 1967번 - 트리의 지름 ( C++ )

3. 풀이

---

트리 이므로 부모-자식 간의 edge만 존재하니, 다익스트라처럼 여러 번 연산을 하지 않아도 된다.

단지, 방문했는지 여부를 체크하면 끝!

 

가장 먼 점을 구할 땐, dfs를 사용하여 계산한다.

4. 코드

---

#include <iostream>
#include <vector>
#include <string.h>
using namespace std;

vector<pair<int, int>> V[10001];
bool visited[10000] = { false, };

int res = 0;
int endPoint = 0;

void dfs(int start, int len) {
	if (visited[start]) return;

	visited[start] = true;

	if (res < len) {
		res = len;
		endPoint = start;
	}

	for (int i = 0; i < V[start].size(); i++)
	{
		dfs(V[start][i].first, len + V[start][i].second);
	}
}

int main()
{
	int n;
	cin >> n;

	if (n == 1)
	{
		cout << 0;
		return 0;
	}

	int parent, child, cost;

	// edge 수는 n-1.
	for (int i = 0; i < n - 1; i++)
	{
		cin >> parent >> child >> cost;

		V[parent].push_back({ child, cost });
		V[child].push_back({ parent, cost });
	}
	
	// 루트에서 제일 먼 점 A구하기.
	dfs(1, 0);

	memset(visited, false, sizeof(visited));

	// 점 A에서 가장 먼 점 구하기.
	dfs(endPoint, 0);

	cout << res;
}

 

V라는 벡터에 저장할 때, V[parent] 말고도, V[child]로 한번 더 저장해서

부모 -> 자식 / 자식 -> 부모 노드 방향 등 어느 방향에서 접근하더라도 계산 가능하도록 한 점이 인상적이었다!