[백준] 골드5 : (1068) 트리 [반례 O]

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

 

다음과 같은 예외 사항을 염두에 두고 풀어야 한다.

반례

#1: Root 노드가 0번 노드가 아닌 경우
이 문제에서는 트리의 순서가 번호 순서대로 투르 -> 자손으로 입력이 주어진다는 보장이 없다.
또한, 테스트 케이스에서는 이진 트리 처럼 설명하지만, 꼭 이진 트리로 입력이 주어진다는 보장이 없다.

5
1 3 1 -1 3
2
Answer: 2

4
3 2 -1 2
0
Answer: 2


#2: 삭제될 노드의 부모 노드가 리프 노드가 될 수 있다.
트리의 성질을 보면, 자손이 없는 노드는 리프 노드이다.
자손이 1개뿐인 노드에서 이 1개의 노드가 제거된다면 부모 노드가 리프 노드가 된다.

2
1 -1
0
Answer: 1

5
1 2 3 4 -1
3
Answer: 1


#3: Root 노드를 삭제하면 리프 노드는 0개이다.
Root 노드가 리프 노드가 될 수는 있지만, Root 노드가 제거되는 경우에는 리프 노드가 없어진다.

2
1 -1
1
Answer: 0

1
-1
0
Answer: 0

 

 

이 문제는 자손 노드가 리프 노드인지 DFS를 통해 검사하여 풀었다.

 

각 노드마다, 자손 노드의 번호를 저장한다.

기존의 리프 노드의 개수를 구한다. (삭제 로직을 수행하기 전)

• 각 노드 번호마다 검사하여 자손 노드 없는지 검사한다. 없으면 리프 노드의 개수를 1개 올린다.
• 자손 노드가 1개인 노드의 자손 노드가 삭제될 노드라면, 리프 노드의 개수를 1개 올린다.
  
  • 자손 노드가 삭제되면 자신이 리프 노드가 되기 때문이다.
• 삭제할 노드를 기준으로 DFS를 수행한다.
  • 현재 노드의 자손 노드가 없는 경우, 자신이 리프 노드이기 때문에 리프 노드의 개수를 1개 뺀다.
  • 현재 노드의 자손 노드를 모두 순회하여 이를 반복한다.

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

void Func(map<int, vector<int>>& Node, int CurNode, int& LeafNode)
{
	// 현재 노드의 자손 노드가 없는 경우, 리프 노프 -1
	if (Node[CurNode].empty())
	{
		LeafNode--;
		return;
	}

	// 현재 노드의 자손 노드를 전부 순회
	for (int i = 0; i < Node[CurNode].size(); ++i)
		Func(Node, Node[CurNode][i], LeafNode);
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, Remove;
	cin >> N;

	// 노드, 자손 노드
	map<int, vector<int>> Node;
	for (int i = 0, j; i < N; ++i)
	{
		cin >> j;
		Node[j].emplace_back(i);
	}

	cin >> Remove;

	// 기본 리프 노드의 개수를 구함
	int LeafNode = 0;
	for (int i = 0; i < N; ++i)
	{
		// 자손이 없는 경우, 리프 노드 +1
		if (Node[i].empty())
		{
			LeafNode++;
			continue;
		}

		// 자손 노드가 1개인 노드의 자손 노드가 삭제 노드인 경우
		if (Node[i].size() == 1)
		{
			// 자손 노드가 삭제되면 자신이 리프 노드가 되기 때문에, 리프 노드 +1
			Node[i][0] == Remove ? LeafNode++ : 0;
		}
	}

	// 제거 노드 기준으로 이어진 노드들에서 리프 노드 검사 후 빼줌
	Func(Node, Remove, LeafNode);

	cout << LeafNode << "\n";
}