백준 1068번 : 트리

[문제 링크]

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

---

간단한 그래프 탐색 문제였다.

리프노드를 찾는 탐색은 부모노드에서 자식노드 방향으로의 탐색만 필요하기 때문에 단방향 그래프로 구성하였고,
트리 구조로 구성된 그래프 특성 상 간선의 수가 많지 않다는 특징이 있기 때문에 인접리스트로 그래프를 표현하여 공간복잡도를 최적화하였다.

 

한가지 예외사항으로 루트노드가 제거될 경우 트리 자체가 제거되기 때문에 루트노드와 제거한 노드를 비교하는 로직을 추가하였다.

---

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

int getLeafNodeCount(const vector<vector<int>>& tree, int rootNode)
{
	int LeafNodeCnt = 0;

	//DFS
	vector<bool> visited(tree.size());

	stack<int> stk;
	stk.push(rootNode);
	visited[rootNode] = true;

	while (!stk.empty())
	{
		int here = stk.top();
		stk.pop();

		if (tree[here].empty())
			LeafNodeCnt++;
		else
		{
			for (const int child : tree[here])
			{
				if (!visited[child])
				{
					stk.push(child);
					visited[child] = true;
				}
			}
		}
	}

	return LeafNodeCnt;
}

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

	vector<vector<int>> tree(N);
	int rootNode = -1;

	for (int i = 0; i < N; i++)
	{
		int parent;
		cin >> parent;

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

	int removeNode;
	cin >> removeNode;

	for (auto& parentTree : tree)
	{
		bool isRemoved = false;
		for (vector<int>::iterator iter = parentTree.begin(); iter != parentTree.end(); iter++)
		{
			if (*iter == removeNode)
			{
				parentTree.erase(iter);
				isRemoved = true;
				break;
			}
		}
		if (isRemoved)
			break;
	}

	if (rootNode == -1 || rootNode == removeNode)
		cout << 0;
	else
		cout << getLeafNodeCount(tree, rootNode);

	return 0;
}