[코딩테스트] [BOJ1068] 트리

문제

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

---

풀이

1. 연결된 자식 노드를 삭제해야하기 때문에 자식 노드 입장에서 연결된 부모 노드를 알 필요가 없다 => 부모 노드에 연결된 자식 노드만 표현한 그래프 만들기

2. 지워야 할 노드를 입력받고, 해당 노드로부터 bfs 수행해서 삭제 표시

3. 만약 지워야 할 노드가 루트 노드라면, 남는 리프 노드가 하나도 없으므로 0 출력하고 함수 종료

4. 루트 노드로부터 bfs 수행해서 남은 리프 노드 개수 증가
   4-1. 현재 노드와 연결된 노드를 탐색하며 삭제 표시가 되어있지 않는 자식 노드가 있다면 childCount 증가
   4-2. childCount가 0이면 자식 노드가 없거나 있더라도 삭제 처리 되었다는 뜻이기에 lefaCount 증가

---

코드

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

int main()
{
	int nodeCount = 0;
	cin >> nodeCount;

	vector<vector<int>> adj(nodeCount);
	int rootNode = -1;
	for (int i = 0; i < nodeCount; i++)
	{
		int parent = 0;
		cin >> parent;

		if (parent != -1)
		{
			adj[parent].push_back(i);
		}
		else
		{
			rootNode = i;
		}
	}

	int removeNode = 0;
	cin >> removeNode;
	
	vector<bool> isRemove(nodeCount, false);
	queue<int> removeBfs;
	removeBfs.push(removeNode);

	while (!removeBfs.empty())
	{
		int current = removeBfs.front();
		isRemove[current] = true;
		removeBfs.pop();

		for (int next : adj[current])
		{
			if (!isRemove[next])
			{
				removeBfs.push(next);
			}
		}
	}

	if (removeNode == rootNode)
	{
		cout << 0;
		return 0;
	}

	int leafCount = 0;

	queue<int> leafBfs;
	leafBfs.push(rootNode);
	
	while (!leafBfs.empty())
	{
		int current = leafBfs.front();
		leafBfs.pop();

		int childCount = 0;
		for (int next : adj[current])
		{
			if (!isRemove[next])
			{
				leafBfs.push(next);
				childCount++;
			}
		}

		if (childCount == 0)
		{
			leafCount++;
		}
	}
	
	cout << leafCount;

	return 0;
}