[C/C++] 백준 - 20924번 : 트리의 기둥과 가지

문제

시청 공무원 마이크로는 과장으로부터 시에 있는 나무의 기둥의 길이와 가장 긴 가지의 길이를 파악하라는 업무 지시를 받았다.

마이크로는 ICPC Sinchon Winter Algorithm Camp에서 배운 트리 자료 구조를 이용하면 이 작업을 좀 더 수월하게 할 수 있으리라 판단했다. 

마이크로는 트리의 기둥과 가지를 분류하기 위해 기가 노드를 추가로 정의하였다.

기가 노드는 루트 노드에서 순회를 시작했을 때, 처음으로 자식 노드가 2$2$개 이상인 노드다. 기둥-가지를 줄여 기가 노드라 이름 붙였다. 위 그림에서 기가 노드는 4$4$번 노드다.

단, 위 그림과 같이 리프 노드가 단 1$1$개인 경우 리프 노드가 동시에 기가 노드가 된다.

또한, 위 그림과 같이 루트 노드가 동시에 기가 노드인 경우도 가능하다.

• 트리의 기둥은 루트 노드에서부터 기가 노드까지다. 위 그림에서 기둥은 1−2−3−4$1-2-3-4$ 이다.
  기둥의 길이는 기둥의 간선 길이의 합인 1+2+3=6$1 + 2 + 3 = 6$ 이 된다.
• 트리의 가지는 기가 노드에서부터 임의의 리프 노드까지다. 위 그림에서 가지는 4−5−6−7$4-5-6-7$, 4−5−8$4-5-8$, 4−9$4-9$, 4−10−11$4-10-11$, 4−10−12$4-10-12$ 총 5$5$개가 있다.
  가지의 길이는 가지의 간선 길이의 합이다. 다행히도 가장 긴 가지의 길이 하나만 기재하면 된다. 4−10−12$4-10-12$ 가지가 간선 길이의 합 3+3=6$3 + 3 = 6$ 으로 가장 긴 가지이다.

마이크로는 시의 나무를 트리 자료 구조로 옮겼다. 그런데 과장이 마이크로에게 또 다른 업무를 지시했다! 너무 바쁜 마이크로를 대신해 트리의 기둥과 가장 긴 가지의 길이를 측정하자.

 

 

 

처음에는 유향 그래프로 작성해서 매우 쉽게 해결될 거라고 생각했는데 역시 바로 틀렸고

무향 그래프로 해야한다는 걸 깨달은 후 코드를 수정하였다.

 

만약 루트노드가 1인데 입력으로 2 1 3이 주어질 경우 유향 그래프 코드로 작성하면 이러한 경우에 반례가 생겨버린다. 따라서 모든 간선 정보를 무향 그래프로 구현해주어야한다.

 

나머지는 모두 간단한 탐색 형태로 DFS로 작성하면 쉽게 해결이 가능하다.

#include <iostream>
#include <queue>
#include <vector>
#include <stack>
#include <string>
#include <cstring>
#include <sstream>
#include <set>
#include <unordered_set>
#include <map> 
#include <algorithm>
#include <cmath>
#include <ctime>
#define fastio ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define ENDL cout << endl
#define ll long long
#define ull unsigned long long
#define INF 987654321
#define Mod 1000000007
#define endl '\n'

using namespace std;

int subRoot;
bool visited[200003];
ll length, answer = -INF;
vector<pair<int, int>> treeNode[200003];

void pilar(int node, ll cost) {
	queue<int> q;
	int nextCost = 0;
	visited[node] = true;
	for (int i = 0; i < treeNode[node].size(); i++) {
		if (!visited[treeNode[node][i].first]) {
			q.push(treeNode[node][i].first);
			nextCost += treeNode[node][i].second;
		}
	}
	
	if (q.size() >= 2 || q.size() == 0) {
		subRoot = node;
		length = cost;
		return;
	}
	int next = q.front(); q.pop();
	pilar(next, cost + nextCost);
}

void leafNode_cost(int index, ll cost) {
	visited[index] = true;
	// 리프 노드까지 노달
	bool flag = false;
	for (int i = 0; i < treeNode[index].size(); i++) {
		if (!visited[treeNode[index][i].first]) flag = true;
	}
	if (!flag) {
		answer = max(answer, cost);
		return;
	}

	for (auto& ptr : treeNode[index]) {
		if (!visited[ptr.first]) {
			leafNode_cost(ptr.first, cost + ptr.second);
		}
	}
}

int input() {
	int N, Root;
	cin >> N >> Root;
	for (int i = 0; i < N - 1; i++) {
		int from, to, cost;
		cin >> from >> to >> cost;
		treeNode[from].push_back({ to, cost });
		treeNode[to].push_back({ from, cost });
	}
	return Root;
}

void result() {
	cout << length << " " << answer << endl;
}

int main() {
	fastio;
	int root = input();
	pilar(root, 0);
	leafNode_cost(subRoot, 0);
	result();

	return 0;
}