[BOJ] 트리(1068)

www.acmicpc.net/problem/1068

1068번: 트리

분류-트리, DFS

난이도-골드5

본 문제는  다른 언어로도 풀이되었습니다.

JavsScript 풀이 보러가기 -> 2021.05.06 - [알고리즘/BOJ 풀이(JS)] - [BOJ] 트리(1068)

 

문제

트리에서 리프 노드란, 자식의 개수가 0인 노드를 말한다.

트리가 주어졌을 때, 노드 하나를 지울 것이다. 그 때, 남은 트리에서 리프 노드의 개수를 구하는 프로그램을 작성하시오. 노드를 지우면 그 노드와 노드의 모든 자손이 트리에서 제거된다.

예를 들어, 다음과 같은 트리가 있다고 하자.

현재 리프 노드의 개수는 3개이다. (초록색 색칠된 노드) 이때, 1번을 지우면, 다음과 같이 변한다. 검정색으로 색칠된 노드가 트리에서 제거된 노드이다.

이제 리프 노드의 개수는 1개이다.

입력

첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다. 셋째 줄에는 지울 노드의 번호가 주어진다.

출력

첫째 줄에 입력으로 주어진 트리에서 입력으로 주어진 노드를 지웠을 때, 리프 노드의 개수를 출력한다.

예제 입력 1 복사

5 -1 0 0 1 1 2

예제 출력 1 복사

2

예제 입력 2 복사

5 -1 0 0 1 1 1

예제 출력 2 복사

1

예제 입력 3 복사

5 -1 0 0 1 1 0

예제 출력 3 복사

0

예제 입력 4 복사

9 -1 0 0 2 2 4 4 6 6 4

예제 출력 4 복사

2

풀이

※ C++로 먼저 풀고 JavaScript로 풀었는데 여러의미로 환장할 뻔했다..

※ 주의사항

 - 이진트리 아님 주의...

 

1. Node 클래스는 index번호와 자식노드들을 저장하는 children배열로 이루어져 있다.

2. 부모노드를 가리키는 입력(2번째 줄)을 확인하며 nodes[부모노드]의 children에 index(입력 순서)를 추가해 준다.

3. dfs는 root 부터 시작해서 children이 하나도 없거나 하나 있는데 그 노드가 삭제노드(del)일 경우에 리프노드 이기 때문에 1을 반환한다.

3. 그렇지 않은 노드들에 대해서는 children(자식노드 인덱스)을 순회하며 삭제노드(del)가 아닐 경우에 dfs재귀를 돌려서 그 합을 return 한다.

4. 만약 root==del일 경우 삭제가 dfs가 끝까지 돌기 때문에(삭제를 안한 것 처럼) 삼항연산자로 0을 출력해 주고 root!=del일 경우 dfs의 반환값을 출력한다.

 

※ del과 인덱스에 따라서 return 하거나 계산하지 않고 넘어가는 것은 안전장치를 많이 3가지 해놔서 조금 비 효율적일 수 있다..

 

코드

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

int N;
int del;
typedef struct NODE {
	int no;
	vector<int> children;
}NODE;
vector<NODE> arr;
int dfs(int root) {
	if (arr[root].children.size() == 0) return 1; // 리프노드
	if (arr[root].children.size() == 1 && arr[root].children[0] == del) return 1;
	// 하나 있는 자식을 지우면 리프노드가 된다.

	int ans = 0;
	for (int i = 0; i < arr[root].children.size(); i++) {
		int child = arr[root].children[i];
		if (child == del) continue;
		ans += dfs(child);
	}
	return ans;
}
int main() {
	cin.tie(0); cout.tie(0);
	ios_base::sync_with_stdio(0);
	cin >> N;
	arr.resize(N, {-1,vector<int>(0)});

	int temp;
	int root;
	for (int i = 0; i < N; i++) {
		arr[i].no = i;

		cin >> temp;		// i번째 노드의 부모노드

		if (temp < 0) 
			root = i;
		else							// 자식이 하나면
			arr[temp].children.push_back(i);

	}
	cin >> del;
	cout << (del == root ? 0 : dfs(root));

	return 0;
}