[BOJ] 1068 : 트리 - travelbeeee

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

---

[ 알고리즘풀이 ]

- 정의)

graph[X][Y] := X가 Y의 부모 노드면 1, 아니면 0.

( 즉, 부모가 자식에게 간선을 이음. )

 

1. 지워야하는 노드(del) 을 입력받으면, del 에서 BFS 탐색을 이용해 가능한 모든 노드를 탐색한다. 즉, del 의 자식, 자손들을 모두 탐색하면서 지워지는 노드로 check하고 graph 를 갱신한다.

2. 갱신된 graph 를 탐색하면서 지워지지 않은 노드별로 자식의 개수를 카운트한다.

3. 지워지지않고, 자식이 없는 노드들만 카운트한다.

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

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int N, j, del, sub[50] = {};
	bool graph[50][50] = {};
	bool checkDel[50] = {};

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> j;
		if (j == -1)
			continue;
		graph[j][i] = 1;
	}
	cin >> del;

	queue<int> q;
	q.push(del);
	while (!q.empty()) {
		int s = q.front();
		checkDel[s] = 1;
		q.pop();
		for (int i = 0; i < N; i++)
			graph[i][s] = 0;
		for (int j = 0; j < N; j++)
			if (graph[s][j])
				q.push(j);
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++)
			if (graph[i][j])
				sub[i]++;
	}

	int ans = 0;
	for (int i = 0; i < N; i++) {
		if (checkDel[i])
			continue;
		if (sub[i] == 0)
			ans++;
	}
	cout << ans;
}

---