[백준] 1167번 트리의 지름

1. 문제

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

트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오.

입력으로는 노드의 개수 N과 간선의 정보가 주어진다.

문제는 말 그대로 트리에서 임의의 두 점 사이 거리 중 가장 긴 것을 구하면 된다.
같은 이름의 다른 문제 (1967번 트리의 지름)가 하나 더 있는데 이 문제와의 차이점은 트리의 루트 노드가 주어지냐 안주어지냐의 차이점이다.

2. 풀이

임의의 점(N1)을 하나 잡고 가장 먼 노드(N2)를 찾고, 다시 그 노드에서 가장 먼 노드(N3)까지의 거리가 최대의 거리다

이를 이용하여 임의의 점을 잡고 DFS 탐색을 하여 가장 먼 노드(N)를 찾고, 다시 찾은 노드(N)으로 부터 가장 먼 노드까지의 거리를 찾으면 된다.

3. 코드

#include <iostream>
#include <vector>
#include <array>
#include <algorithm>

using namespace std;

int N, maxLen = 0, maxPos;
vector<vector<pair<int, int>>> grid;
array<int, 1000001> visit;

void dfs(int cur, int len)
{
	visit[cur] = true;

	if (maxLen < len)
	{
		maxPos = cur;
		maxLen = len;
	}

	for (const auto i : grid[cur])
	{
		if (visit[i.first] == false)
			dfs(i.first, len + i.second);
	}
}

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

	cin >> N;
	grid.assign(N + 1, {});

	for (int i = 1; i <= N; ++i)
	{
		int idx, tmp = 0, val;
		cin >> idx;
		cin >> tmp;
		while (tmp != -1)
		{
			cin >> val;
			grid[idx].push_back(make_pair(tmp, val));
			cin >> tmp;
		}
	}

	dfs(1, 0);
	visit.fill(false);
	dfs(maxPos, 0);

	cout << maxLen;
}

4. 후기

루트 노드가 주어진 1967번 트리의 지름은 트리의 자식 노드에 대해 DFS를 돌리면서 거리를 찾아가면 된다.

하지만 지금 풀이를 하는 1167번 트리의 지름은 루트노드가 주어지지 않는다.

때문에 처음 풀이를 했을때는 반복문으로 N개의 노드가 각각 루트일 경우를 모두 DFS로 돌리면서 풀어봤지만 역시나 시간초과였다.

이 문제는 도져히 아이디어가 생각이 안나서 결국 힌트를 찾아본 문제였다.

그리고 이 해법의 힌트를 제공해주는 글과 수학적으로 증명해주는 정말 고마운 두 분의 글을 소개하며 마치겠다.

https://www.acmicpc.net/board/view/83695 (백준 힌트 제공)
https://blog.myungwoo.kr/112 (해당 알고리즘의 증명)