[백준/BOJ] 백준 8872번 : 빌라봉

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

8872번: 빌라봉

 

가장 지름이 큰 트리의 중점에, 나머지 트리의 중점을 길이 L인 간선을 붙여 연결을 해야지, 임의 두 정점 사이를 오가는데 최대 시간이 최소가 된다. 그렇게 되면 최종적으로 연결된 트리에서 두 정점 사이를 오가는데 최대 시간이 될 수 있는 경우는 다음과 같이 3가지이다.

 

1. 가장 큰 트리의 지름

2. 가장 큰 트리의 반지름 + 두 번째로 큰 트리의 반지름 + L

3. 두 번째로 큰 트리의 반지름 + L + 세 번째로 큰 트리의 반지름 + L 

 

즉, 이 세 가지 경우중 가장 큰 값을 구해 문제를 해결했다.

 

트리의 지름은 해당트리의 임의의 지점에서 가장 먼 지점 a를 구하고 a에서 가장 먼 지점 b를 구하여 a와 b사이의 거리를 통해 구했고, 트리의 반지름은, 해당 트리에서 임의의 정점을 중점이라고 가정하고 해당 정점에서 a, b 까지 거리 중 더 큰 거리가 최소가 되는 해당 지점과의 거리를 통해 트리의 반지름을 구했다.

 

코드

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

int n, m, l;
vector<pair<int, int>> adj[100005];
int tree_id[100005]; //[정점] = 트리id
int tree_cnt = 0;

vector<int> tree_node[100005]; //[트리id] = 해당 트리에 속한 노드

int visited[100005][3];
int dist[100005][3];

int tree_diameter[100005]; //[트리id] = 트리의 지름
int tree_radius[100005]; //[트리id] = 트리의 반지름

//각 정점이 어떠한 트리에 속하는지 파악하고
//가장 지름이 큰 트리의 중점에 나머지 트리의 중점을 L 길이로 연결한다고 생각
//그렇다면 정답이 될 수 있는 경우는 아래와 같이 3가지 경우
//1.가장 큰 트리의 지름
//2.가장 큰 트리의 반지름 + 2번째로 큰 트리의 반지름 + L
//3.2번째로 큰 트리의 반지름 + L + 3번째로 큰 트리의 반지름 + L 

void make_tree_id(int here, int id) {
	tree_id[here] = id;
	tree_node[id].push_back(here);

	for (int i = 0; i < adj[here].size(); i++) {
		int there = adj[here][i].second;

		if (tree_id[there] == 0) {
			make_tree_id(there, id);
		}
	}
}

void dfs(int here, int kind, int cost_sum) {
	visited[here][kind] = 1;
	dist[here][kind] = cost_sum;

	for (int i = 0; i < adj[here].size(); i++) {
		int there = adj[here][i].second;
		int cost = adj[here][i].first;

		if (visited[there][kind] == 0) {
			dfs(there, kind, cost_sum + cost);
		}
	}
}

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n >> m >> l;
	for (int i = 0; i < m; i++) {
		int a, b, t;
		cin >> a >> b >> t;

		adj[a].push_back(make_pair(t, b));
		adj[b].push_back(make_pair(t, a));
	}

	//각 정점이 어떠한 트리에 속하는지 파악하기
	for (int i = 0; i < n; i++) {
		if (tree_id[i] == 0) {
			tree_cnt++;
			make_tree_id(i, tree_cnt);
		}
	}

	for (int i = 1; i <= tree_cnt; i++) {
		//트리의 지름을 구한다
		//해당트리의 임의의 지점(start)에서 가장 먼 지점 a를 구하고
		//a에서 가장 먼 지점 b를 구하여 a와 b사이의 거리로 지름을 구한다
		int start = tree_node[i][0];

		dfs(start, 0, 0);
		int a = start;
		int a_dist = 0;
		for (int j = 0; j < tree_node[i].size(); j++) {
			int node = tree_node[i][j];
			if (a_dist < dist[node][0]) {
				a_dist = dist[node][0];
				a = node;
			}
		}

		dfs(a, 1, 0);
		int b = a;
		int b_dist = 0;
		for (int j = 0; j < tree_node[i].size(); j++) {
			int node = tree_node[i][j];
			if (b_dist < dist[node][1]) {
				b_dist = dist[node][1];
				b = node;
			}
		}

		dfs(b, 2, 0); //b노드에서 속한 트리의 정점까지 거리도 구한다

		tree_diameter[i] = b_dist; //트리의 지름

		//트리의 반지름을 구하기 위해 트리에서 임의의 중점을 가정하고, 반지름을 구한다
		tree_radius[i] = tree_diameter[i];
		for (int j = 0; j < tree_node[i].size(); j++) {
			int node = tree_node[i][j]; //node를 트리의 중점이라고 가정

			//node가 트리의 지름 경로에 속하는지 확인
			//node와 a,b 사이의 거리를 구해서 반지름을 구한다
			//트리의 반지름은 임의의 지점(node)에서, a,b중 최대 거리가 최소가 되는 지점
			tree_radius[i] = min(tree_radius[i], max(dist[node][1], dist[node][2]));
		}
	}

	sort(tree_diameter + 1, tree_diameter + 1 + tree_cnt);
	sort(tree_radius + 1, tree_radius + 1 + tree_cnt);

	int result = tree_diameter[tree_cnt]; //1. 가장 큰 트리의 지름
	if (tree_cnt >= 2) {
		result = max(result, tree_radius[tree_cnt] + tree_radius[tree_cnt - 1] + l); //2. 가장 큰 트리의 반지름 + 2번째로 큰 트리의 반지름 + L
	}

	if (tree_cnt >= 3) {
		result = max(result, tree_radius[tree_cnt - 1] + l + tree_radius[tree_cnt - 2] + l); //3. 2번째로 큰 트리의 반지름 + L + 3번째로 큰 트리의 반지름 + L 
	}

	cout << result;

	return 0;
}