2023.1.26.(목)

문제

problem

접근 방법

우리는 트리 문제를 해결하고 있습니다.

먼저 노드들이 입력 되었을 때, 그 노드들 간의 연결을 나타낼 수 있어야겠죠. 벡터 배열 tree를 하나 만들고, 각 인덱스를 노드로 하여금 연결된 다른 노드들을 인덱스 공간에 push 하여 넣습니다.

vector<int> tree[51];

int parent; 
for (int i = 0; i < N; i++) {
    cin >> parent; 
    input[i] = parent; 
    if (parent == -1) continue; 
    else tree[parent].push_back(i);
}

그 다음에, 우리는 삭제할 노드 del을 입력 받게 됩니다. 우리는 tree[del]에서 시작합니다. roots 배열의 공간들은 모두 0으로 초기화 합니다.

큐 que에 del을 넣고, tree[del] 벡터에 들어 있는 모든 수들을 que에 차례대로 push 합니다. roots[que.front()]에는 -1 을 집어 넣어, 노드 번호 que.front()가 더이상 존재하지 않음을 나타냅니다. 모든 수들이 push 되었다면, que.pop()을 하여 다음 수로 넘어갑니다.

이렇게 que가 모두 비워질 때까지 해당 과정을 반복합니다. 그러면 roots에는 각 인덱스에 해당하는 노드가 없다면 공간이 모두 -1로 채워져 남아 있게 됩니다. 나머지 노드들에는 자식 수만큼이 들어 있게 될 테지만요.

남아 있는 문제

이제 우리는 어떤 노드들이 더이상 루트 노드와 연결되어 있지 않은지를 압니다. 하지만 del 노드의 부모 노드의 자식 수는 아직 갱신이 안되었습니다. 우리는 처음에 tree 배열의 인덱스를 부모 노드로 한 후에, 자식 노드들을 각 공간에 넣어두었었죠. 하지만 이대로는 거꾸로 인덱스 노드의 부모 노드를 알아낼 수가 없습니다. 즉, del 노드를 삭제 한 후에 del 노드의 부모 노드의 자식 수를 하나 줄이는 것에서 어려움이 있는 것입니다.

따라서 만든 것이 input 배열입니다. 입력을 받을 때, 각 인덱스 노드의 부모 노드를 저장해 두는 것입니다. 위의 과정을 반복한 후에 마지막으로 del 노드의 부모 노드의 자식 수에서 1을 뺀 값을 부모 노드 인덱스에 갱신을 해주어야 합니다.

코드

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

int main()
{
	int N;
	cin >> N; 

	vector<int> tree[51];
	int roots[51] = {0};
	int input[51] = {0};

	int parent; 
	for (int i = 0; i < N; i++) {
		cin >> parent; 
		input[i] = parent; 
		if (parent == -1) continue; 
		else {
			tree[parent].push_back(i);
		} 
	}

	for (int i = 0; i < N; i++) {
		roots[i] = tree[i].size(); 
	}

	int del;
	cin >> del; 

	queue<int> que;
	que.push(del); 

	int index; 

	while (!que.empty()) {

		index = que.front();
		while (tree[index].size() > 0) {
			que.push(tree[index].back()); 
			tree[index].pop_back();
		}
		roots[index] = -1;
		que.pop(); 
	}


	if (input[del] >= 0) {
		roots[input[del]]--;

		for (int i = 0; i < N; i++) {
			if (roots[i] < 0) roots[i] = -1; 
		}

		int count = 0; 

		for (int i = 0; i < N; i++) {
			if (roots[i] == 0) count++; 
		}

			cout << count;
	} else {
		cout << 0; 
	}

	
}