[Baekjoon] 1068번: 트리

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

1068번: 트리

 

---

 

문제 해결 과정

착안

트리 내의 $i$번째 노드에 대해 방문 여부를 표시하면서 삭제될 노드인지를 확인 및 표시하고, 이러한 과정을 부모 노드가 존재하는 경우 재귀적으로 반복 수행하고자 하였다.

 

구현

위의 방법과 같이 트리 내의 모든 노드에 대해 재귀적으로 상위 노드로 접근하는 경우는 중복된 노드를 계속해서 방문하게 되어 알고리즘의 시간 복잡도가 증가하게 되므로, 노드의 방문 여부를 별도로 표시하여 이미 방문한 노드를 발견하면 더이상 상위 노드로 접근하지 않도록 구현하였다.

 

한편, 위와 같은 방법에서 말단 노드를 구분할 수 있도록 별도의 변수를 사용하였다. 따라서, 삭제될 노드 여부를 모두 파악한 다음, 삭제 표시가 된 노드의 부모 노드(루트 노드가 아닌 경우)에 접근하여 자식 노드의 수를 1씩 감소시킨 뒤 최종적으로 자식 노드의 수가 0인 노드의 수를 카운팅하여 출력하였다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>
#include <queue>

using namespace std;

struct Node
{
	int Parent;
	int NumChild;
	bool Visited;
	bool Deleted;
};

Node Tree[50];
queue<int> q;
int LeafCount;

void Find(int idx)
{
	int current = idx;
	bool isdel = false;

	while (true)
	{
		q.push(current);
		Tree[current].Visited = true;
		
		if (Tree[current].Deleted)
		{
			isdel = true;
			break;
		}

		if (Tree[current].Parent == -1)
			break;

		current = Tree[current].Parent;
		if (Tree[current].Visited)
		{
			if (Tree[current].Deleted)
				isdel = true;

			break;
		}
	}

	if (isdel)
	{
		while (!q.empty())
		{
			int i = q.front();
			q.pop();

			Tree[i].Deleted = true;
		}
	}
	else
		q = queue<int>();
}

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

	for (int i = 0; i < N; i++)
	{
		cin >> Tree[i].Parent;
		if (Tree[i].Parent >= 0)
			Tree[Tree[i].Parent].NumChild++;
	}

	int deleted;
	cin >> deleted;
	Tree[deleted].Deleted = true;

	for (int i = 0; i < N; i++)
		if (Tree[i].Visited == false)
			Find(i);

	for (int i = 0; i < N; i++)
		if (Tree[i].Deleted)
			if (Tree[i].Parent != -1)
				Tree[Tree[i].Parent].NumChild--;

	for (int i = 0; i < N; i++)
		if (Tree[i].NumChild == 0 && Tree[i].Deleted == false)
			LeafCount++;
	
	cout << LeafCount << "\n";
	return 0;
}

 

실행 결과