C++ / 백준 / 20924 / 트리의 기둥과 가지

문제

 

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

20924번: 트리의 기둥과 가지

 

 

문제풀이

 

입력되는 여러 가지 형태의 나무이다. 나무는 가지 없이 기둥만 있을 수 있다.

나무의 가지가 여러 개 있을 경우 가장 긴 가지의 길이만 필요하다.

입력되는 노드 두 개는 누가 부모인지 모른다. 따라서 node1의 트리와 node2의 트리의 각각 node를 추가해야 한다.

 

vector<vector<pii>>tree;
vector<bool>visited;
vector<int>remain_node;
int wood_strut, longest;
bool isFound;

tree는 트리이다. tree[부모노드]={자식노드, 길이}로 구성된다.

visited는 해당 노드의 방문여부를 나타내는 bool형 벡터이다.

remain_node는 해당 노드의 남은 자식수를 나타내는 벡터이다. 반복문 없이 바로 남은 노드의 개수를 알기 위해 사용했다.

wood_strut는 나무기둥의 길이를 나타내는 변수, longest는 가장 긴 가지의 길이를 나타내는 변수이다.

isFound는 나무기둥을 찾았는지를 나타내는 bool형 변수이다.

 

	int node1(0), node2(0), dist(0);
	for (int idx = 1; idx < N; ++idx) {
		cin >> node1 >> node2 >> dist;
		tree[node1].push_back({ node2, dist });
		tree[node2].push_back({ node1, dist });
		++remain_node[node1];
		++remain_node[node2];
	}

	visited[root_node] = true;
	DFS(root_node, 0);

먼저 메인문이다.

node 두 개를 입력받고 tree에 각각 노드와 길이를 입력한다. (누가 부모고 자식인지 알 수 없으므로)

남은 자식노드의 개수를 나타내는 remain_node에도 각각 1씩 더한다.

루트 노드는 방문여부를 표시한 채로 DFS함수를 실행한다.

 

void DFS(int node, int dist) {
	if (remain_node[node] > 1 && isFound == false) {
		wood_strut = dist;
		dist = 0;
		isFound = true;
	}

DFS는 현재 탐색 중인 node, 현재까지의 길이를 인자로 받는다.

남은 노드가 1개 초과이고 나무기둥을 발견한 적이 없으면 현재 노드가 기가 노드이다.

따라서 나무 기둥의 길이를 갱신해 주고 dist를 0으로, isFound를 true로 바꾼다.

 

	if (remain_node[node] == 0) {
		if (isFound == false) wood_strut = dist;
		else longest = max(longest, dist);
	}

남은 노드가 0이라면 기가노드 또는 리프노드이다.

만약 isFound가 false라면 기가노드이므로 나무 기둥을 갱신해 준다.

isFound가 true라면 리프노드이므로 가장 긴 가지의 길이를 둘 중 큰 값으로 갱신한다.

 

	else {
		for (int idx = 0; idx < tree[node].size(); ++idx) {
			int next_node = tree[node][idx].first;
			int next_dist = tree[node][idx].second;			
			--remain_node[next_node];
			if (visited[next_node] == true)	continue;
			visited[next_node] = true;
			DFS(next_node, dist + next_dist);
		}
	}

만약 남은 노드가 0이 아니라면 else로 올 것이다.
반복문을 통해 남은 자식노드를 탐색한다.

다음 노드의 남은 자식 노드 개수를 하나 감소한다. (자식노드에는 부모노드가 섞여있다.)

방문한 적이 있으면 넘긴다.

그렇지 않으면 DFS함수를 실행한다.

 

 

 

코드

#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;

vector<vector<pii>>tree;
vector<bool>visited;
vector<int>remain_node;
int wood_strut, longest;
bool isFound;

void DFS(int node, int dist) {
	if (remain_node[node] > 1 && isFound == false) {
		wood_strut = dist;
		dist = 0;
		isFound = true;
	}
	if (remain_node[node] == 0) {
		if (isFound == false) wood_strut = dist;
		else longest = max(longest, dist);
	}
	else {
		for (int idx = 0; idx < tree[node].size(); ++idx) {
			int next_node = tree[node][idx].first;
			int next_dist = tree[node][idx].second;			
			--remain_node[next_node];
			if (visited[next_node] == true)	continue;
			visited[next_node] = true;
			DFS(next_node, dist + next_dist);
		}
	}
}


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

	int N(0), root_node(0);
	cin >> N >> root_node;

	isFound = false;
	tree = vector<vector<pii>>(N + 1);
	visited = vector<bool>(N + 1, false);
	remain_node = vector<int>(N + 1, 0);

	int node1(0), node2(0), dist(0);
	for (int idx = 1; idx < N; ++idx) {
		cin >> node1 >> node2 >> dist;
		tree[node1].push_back({ node2, dist });
		tree[node2].push_back({ node1, dist });
		++remain_node[node1];
		++remain_node[node2];
	}

	visited[root_node] = true;
	DFS(root_node, 0);

	cout << wood_strut << " " << longest;
}