백준 - 20924 트리의 기둥과 가지

문제

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

20924번: 트리의 기둥과 가지

트리의 기둥 길이(루트~기가)와 가장 긴 가지의 길이(기가~리프)를 구하는 문제였다.

 

문제 풀이

처음에는 단순하게 size가 2보다 작은 노드가 나올 때까지 dfs를 돌려 기가 노드를 구하고, 기가 노드에서부터 각 노드들까지 dfs를 돌려 가장 긴 가지의 길이를 구하려고 했다. 하지만 루트 노드가 기가 노드와 같을 때 처리를 못해줘서 틀렸었다. 이 부분을 처리하니 맞출 수 있었다.

 

루트 노드가 특이한 경우는 두가지가 있다.

1. 일직선 트리여서 기둥만 있는 경우
   • 이 경우는 findGiga의 종료 조건을 depth가 노드 개수보다 클 때로 잡아주면 간단하게 해결된다.
2. 루트 노드가 기가노드인 경우
   • 이 경우에는 현재 노드가 루트이고, 연결된 노드가 2개 이상일 때 방문처리한 현재 노드를 방문 전으로 되돌리고 루트 노드를 반환해주면 해결된다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>

using namespace std;

/*
1. root, giga 노드 구하기
	- 연결된 노드가 2 이상인 것 : root (tree 아닌 그래프는 입력 아님)
2. dfs로 돌면서 length 구하기
	- 마지막 노드일 경우에 maxLength 갱신
*/

typedef struct Node {
	int n;
	int weight;
}Node;

int N, R; //노드 개수, 루트 번호
vector<vector<Node>> G;
vector<bool> visit;
int rootLength = 0, gigaLenght = 0;

int findGiga(int nowNode, int length, int cnt) { //root에서부터 탐색 시작

	//printf("nowNode: %d\n", nowNode);
	if (G[nowNode].size() > 2 || cnt >= N-1) { //giga node
		rootLength = length;
		return nowNode;
	}

	visit[nowNode] = true;

	if (nowNode == R && G[nowNode].size() > 1) {//맨 앞이 루트면서 기가인 경우
		visit[nowNode] = false;
		return nowNode;
	}


	for (int i = 0; i < G[nowNode].size(); i++) {
		int nextNode = G[nowNode][i].n;
		int nextWeight = G[nowNode][i].weight;
		if (!visit[nextNode]) {
			return findGiga(nextNode, length + nextWeight, cnt+1);
		}
	}
}

void dfs(int nowNode, int length) {
	if (G[nowNode].size() < 2) { //마지막 노드
		gigaLenght = max(length, gigaLenght);
		return;
	}

	visit[nowNode] = true;

	for (int i = 0; i < G[nowNode].size(); i++) {
		int nextNode = G[nowNode][i].n;
		int nextWeight = G[nowNode][i].weight;
		if (!visit[nextNode]) {
			dfs(nextNode, length + nextWeight);
		}
	}
}

int main()
{

	scanf("%d %d", &N, &R);

	G = vector<vector<Node>>(N + 1, vector<Node>());
	visit = vector<bool>(N + 1, false);

	for (int i = 0; i < N - 1; i++) {
		int a, b, d;
		scanf("%d %d %d", &a, &b, &d);

		G[a].push_back({ b,d });
		G[b].push_back({ a,d });
	}

	int giga = findGiga(R, 0, 0);
	//printf("giga: %d\n", giga);

	dfs(giga, 0);

	printf("%d %d", rootLength, gigaLenght);

	return 0;
}

/*
5 1
1 2 100
2 3 10
3 4 1
1 5 7
*/