백준 1068(트리)

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

1068번: 트리

 

어떤 트리에서 어떤 index이하의 subtree를 모두 제거 했을때 리프노드의 갯수를 구하자 

 

 

 

리프노드는 트리에서 자식이 없는 노드를 리프노드라고 한다. 

 

그렇다면 트리를 구성해서, root부터 자식 노드를 방문, 만약에 자식 노드가 없는 경우 +1 하면 된다. 

 

그리고 어떤 index의 subtree를 제거해야 하므로 index를 방문하면 그냥 스킵. 

 

여기서 두가지 상황이 나온다. 

 

만약에 제거해야 하는 인덱스 부모의 자식노드 갯수가 1개인 경우

2개 이상인 경우

	if (index == cant) {
		if (tr[tr[index].parent].children.size() == 1)
			sum++;
		return;
	}

 

만약에 1개인 경우에는 +1을 해준다. 왜냐하면 if문의 순서가 위 코드가 더 상단이라서 자식노드가 1개인 경우 그 자식을 제거하면, 그냥 코드가 끝이다. 그래서 그런 경우만 sum++해줬다. 

 

그리고 인접리스트를 사용하는데 그 이유는 자식노드의 갯수가 몇개인지 모르는 상황에서 인접리스트를 사용하지 않는다면 저장할때 index설정하기가 까다롭다고 생각해서 인접행렬대신 인접리스트로 구현하였다. 

 

#include<iostream>
#include<vector>
using namespace std;
#define MAX 50

int n, tmp, sum, start, cant;

struct tree {
	int parent;
	vector<int> children;
};

struct tree tr[MAX];


void solve(int index) {
	if (index == cant) {
		if (tr[tr[index].parent].children.size() == 1)
			sum++;
		return;
	}
	if (tr[index].children.size() == 0) {
		sum++;
	}
	for (int i = 0; i < tr[index].children.size(); i++) {
		solve(tr[index].children[i]);
	}
}


int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> tmp;
		if (tmp == -1) {
			start = i;
			continue;
		}
		tr[i].parent = tmp;
		tr[tmp].children.push_back(i);
	}
	cin >> cant;
	solve(start);
	cout << sum << "\n";

}