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

Key

• 양의 가중치가 있는 트리가 주어졌을 때 두 노드 사이의 경로 중 가장 긴 경로 구하기
• 노드 개수는 최대 1만개
• 루트 노드는 항상 1번

 

Idea

트리의 지름을 구하는 방법은 다음과 같다.

1. 루트 노드에서 가장 먼 노드 A를 찾는다.
2. 노드 A에서 가장 먼 노드 B를 찾는다.
3. A와 B 사이의 경로가 트리의 지름이 된다.

 

이 문제는 DFS를 두번 활용하면 된다. 우선 두 노드 중 첫번째 노드를 구해보자. 편의상 두 노드를 A, B라고 하겠다. A노드는 루트노드에서 가장 먼 노드를 찾으면 된다. 처음에 왜 루트 노드에서 가장 먼 노드가 A가 되는건지 이해를 못했는데, 간선의 가중치가 양의 정수라서 그렇다. 때문에 거치는 간선 개수가 많아질 수록 경로 길이도 길어진다. 따라서 말단 노드 중 하나가 A 노드일 확률이 높고, 같은 지점에서 출발했을 때 가장 경로 길이가 긴 말단 노드를 구하기 위해 위와 같은 방법을 쓰는 것이다. 

 

다음으로, A에서 다시 가장 먼 노드를 찾으면 된다. 첫 번째 탐색에서 가장 먼 노드를 찾는 과정에서 이미 가능한 최장 경로의 한 끝을 찾았기 때문이다. 이는 A에서 B로 가는 경로가 트리에서 가장 긴 경로라는 것을 보장한다.

 

 

Code

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

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

int maxValue=0, maxNode = 0;

void DFS(int x, int value) {
	int size = node[x].size();
	visited[x] = true;

	if (maxValue < value) {
		maxValue = value;
		maxNode = x;
	
	}

	for (int i = 0; i < size; i++) {
		if (!visited[node[x][i].first]) {
			DFS(node[x][i].first, value+node[x][i].second);
			
		}
	}
}

int main() {

	int N = 0;
	int S = 0, E = 0, W = 0;

	cin >> N;

	for (int i = 0; i < N-1; i++) {
		cin >> S >> E >> W;
		node[S].push_back(make_pair(E, W));
		node[E].push_back(make_pair(S, W));
	}

	DFS(1, 0);

	maxValue=0;
	

	for (int i = 0; i <= N; i++) {
		visited[i] = false;
	}

	DFS(maxNode, 0);

	cout << maxValue << "\n";

	return 0;
}

 

 

회고

DFS를 두번 쓰는 문제를 처음 풀어봐서 어떻게 풀지 감이 안잡혔다. 나중에 다시 풀어봐야겠다. 그리고 fill을 이용해서 배열을 초기화할 수 있다는 걸 처음 알았다. algorithm 헤더를 추가하면 fill(visited, visited+N+1, false) 이렇게 해서 초기화할 수 있다고 한다. 벡터에서만 사용할 수 있는건줄 알았다.