[백준]1068번 트리 - C/C++

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

1068번: 트리

문제

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

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

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

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

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

입력

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

출력

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

---

문제의 예제와 그림을 보고 현혹되지 말아야한다. 문제에는 트리가 이진트리라는 보장이 없고 루트가 0이라는 말도 없다. 이 부분만 인지하면 쉽게 문제를 풀 수 있다.

입력을 받을때 vector의 배열을 이용하여 tree[i] 벡터에 자식 노드들을 push_back 한다. 그다음 root node를 가지고 dfs를 진행한다. 이때 node==k 일 때 -1을 반환하는 이유는 만약 삭제하는 노드가 부모의 유일한 자식이었다면 부모가 leaf node가 되고 그렇지 않다면 leaf node가 되지 않기 때문에 dfs가 -1을 반환하고 size == 1 (자식 노드가 1개)였다면 리프 노드의 수를 하나 더 증가시켜야 한다. 그렇지 않은 일반적인 경우는 tree[node].size() == 0  즉 자식 노드가 없을 때 리프 노드의 수를 하나 증가시켜 준다면 문제를 풀 수 있다.

#include <iostream>
#include <vector>

using namespace std;
int n,k,leaf=0,root;
vector<int> tree[51];


int dfs(int node) {
	if (node == k) return -1;
	if (!tree[node].size()) {
		leaf++;
		return 0 ;
	}
	for (int i = 0; i < tree[node].size(); i++) {
		int tmp = dfs(tree[node][i]);
		if (tmp == -1 && tree[node].size() == 1)
			leaf++;
	}
	return 0;
}

void solve() {
	dfs(root);
	cout << leaf;
}



int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		int t1;
		cin >> t1;
		if (t1 == -1)
			root = i;
		else
			tree[t1].push_back(i);
	}
	cin >> k;
	solve();
	
	return 0;
}

---

문제에서 주어진 조건과 예시로 주어진 것들을 잘 구분해서 문제를 풀어야겠다. 문제를 빠르게 풀어야한다는 생각에 문제를 대충 보고 문제에 명시되지 않은 조건을 생각하거나 생각하지 않는 경우가 있는 것 같다. 이 문제를 풀 때 처음에는 자연스레 일반적인 배열로 이진트리를 구현해나갔으나 마지막 예제를 보니 이진트리가 아니어서 배열을 쓰며 2* node (+1)의 인덱싱을 사용하지 못할 것 같았다. 그래서 벡터로 트리를 처음 표현해보았다. 그다음 생각하지 못한 것은 삭제되는 노드가 유일한 자식일 때 부모 노드가 리프 노드가 된다는 것을 간과하였다. 마지막으로 루트 노드가 주어진 예시에서 모두 0이어서 dfs(0)으로만 시작했는데 문제에는 -1일 때 루트 노드라고 분명히 명시가 되어있었다. 단순히 주어진 예시들에서만 0이 루트 노드였던 것이었다! 오늘도 문제를 풀면서 느낀 점이 많다. 포스팅을 할 때마다 문제를 제대로 읽어야겠다고 한 것 같은데 잘 지켜지지가 않는 것 같다. 새삼스럽지만 또 문제를 잘 읽어야겠다고 다짐한다!