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

문제

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

1967번: 트리의 지름

---

문제 요약

가중치가 있는 트리가 주어졌을 때, 트리의 지름을 출력한다.

 

트리의 지름이란, 트리에 존재하는 모든 경로들 중 가장 긴 것의 길이이다.

---

코드

#include<iostream>
#include<vector>
#include<tuple>
#include<cstring>

#define MAX_N 500000

using namespace std;

int n; 

bool visited[MAX_N + 1];

vector<tuple<int, int>> edges[MAX_N + 1];

int start_node, max_length, max_node;

void dfs(int x, int dist) {
	visited[x] = true;
	
	// 출발 노드에서 가장 먼 노드와 그 노드까지의 거리 갱신
	if (max_length < dist) {
		max_length = dist;
		max_node = x;
	}

	for (int i = 0; i < edges[x].size(); i++) {
		int y, d;
		tie(y, d) = edges[x][i];

		if (visited[y]) continue;

		dfs(y, dist + d);
	}

}

int main() {
	cin >> n;

	// 입력
	for (int i = 0; i < n - 1; i++) {
		int a, b, w;
		cin >> a >> b >> w;
		edges[a].push_back({ b, w });
		edges[b].push_back({ a, w });
	}

	// 루트 노드에서 dfs 진행 -> 가장 먼 노드 찾기
	dfs(1, 0);

	max_length = 0; // 길이 다시 0으로 초기화

	memset(visited, false, MAX_N + 1);

	// 가장 가장 먼 노드에서 다시 dfs 진행 -> 가장 먼 노드에서 가장 먼 노드 찾기
	dfs(max_node, 0); 

	cout << max_length;
	
	return 0;
}

---

코드 설명

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

 

1. 아무 노드에서 DFS를 이용해 시작점에서 가장 먼 노드를 구한다.

 

2. 다시 DFS를 이용해 가장 먼 노드에서 가장 먼 노드를 구한다.

 

3. 두 노드 사이의 거리가 트리의 지름이다.