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

문제 & 링크

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

풀이

1. 임의의 한 노드에서 DFS(깊이 우선 탐색)를 수행하여 가장 먼 노드를 찾는다.

2. 해당 노드(가장 먼 노드)를 시작점으로 다시 한 번 DFS를 수행해 도달할 수 있는 가장 먼 노드를 찾는다.

3. 이때의 거리가 곧 트리의 지름이 된다.

4. 추가적으로 방문 여부를 기록하여 방문했던 노드를 다시 방문하지 않도록 한다.

코드

#include <iostream>
#include <vector>

using namespace std;

vector<pair<int, int>> adj[100001]; // 트리를 인접리스트로 저장
bool visited[100001]; // 방문 여부

int max_dist_n = 1; // 트리의 지름이 되는 끝 노드, 초기값은 임의의 노드로 설정
int max_dist = 0; // 트리의 지름

void dfs(int n, int dist) {
	for (int i = 0; i < adj[n].size(); i++) {	
		if (!visited[adj[n][i].first]) { // 방문하지 않았을 경우
			if (max_dist < dist + adj[n][i].second) { // 현재까지의 거리가 더 클 경우
				max_dist_n = adj[n][i].first; 
				max_dist = dist + adj[n][i].second;
			}

			visited[adj[n][i].first] = true;
			dfs(adj[n][i].first, dist + adj[n][i].second);
		}		
	}
}

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

	int n, nn, d;
	for (int i = 0; i < V; i++) {
		cin >> n;
		while (1) {
			cin >> nn;
			if (nn == -1) break;
			cin >> d;
			
			adj[n].push_back({nn, d});
		}
	}

	visited[max_dist_n] = true;
	dfs(max_dist_n, 0);

	fill(visited, visited + V + 1, false); // visited 배열 초기화
	visited[max_dist_n] = true;
	dfs(max_dist_n, 0);

	cout << max_dist;
}