Baekjoon1068-트리

백준 사이트 1068 - 트리 문제입니다.

1. 문제

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

---

2. Input , Output

---

3. 분류 및 난이도

DFS 문제입니다.
백준에서는 Slive1 난이도를 책정하고 있습니다.

---

4. 생각한 것들

• 트리 구현을 어떻게 할까..?
  • 배열을 사용하면 일자로 트리가 진행될 경우 2^50의 배열의 크기가 필요하므로 배열로 만들 수 없습니다.
  • 그리고 이진트리라는 말이 없으므로 자식이 여러개일 수 있습니다. 벡터를 통해 만들어줍니다.
• DFS 조건문?
  • 트리 자식을 돌아다니다가 remove 값으로 들어온 트리자식을 만나면 return을 해버려 방문을 중단합니다.
  • 만약 자식이 1명이고 마침 그 자식이 제거해야하는 것이면 부모 노드는 리프노드가 되므로 갯수를 세주고 방문을 돌아갑니다.
• 예외가 좀 많아서 정답률이 낮은 것 같습니다.

---

5. code

#include<iostream>
#include<vector>
using namespace std;
vector<int> v[51];
int removenode = 0;
int result = 0;
void DFS(int now)
{
	if (removenode == now)
		return;
	if (v[now].size() == 0)
	{
		++result;
		return;
	}
	else if (v[now].size() == 1)
	{
		if (v[now][0] == removenode)
		{
			++result;
		}
	}
	for (int i = 0; i < v[now].size(); ++i)
		DFS(v[now][i]);
	
}

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

	int n;

	int node = 0;
	int temp = 0;
	int remove = 0;

	cin >> n;
	for (int i = 0; i < n; ++i)
	{
		cin >> temp;
		if (temp != -1)
		{
			v[temp].push_back(i);
		}
		else
			node = i;
	}
	cin >> removenode;
	DFS(node);
	cout << result;
	
	
}

---

6. 후기

DFS같은 재귀는 언제나 어려운것 같습니다.
BFS만세