C++ 백준 1068 트리

백준 1068

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

1068번: 트리

풀이 전 나의 생각

트리가 주어지고, 특정 노드를 삭제 했을 때 나올 수 있는

리프노드의 총 개수를 구해야 한다.

 

조건

- N은 50보다 작거나 같은 자연수

- 만약 부모가 없다면 (루트) -1이 주어진다.

 

과정

문제의 이름이 트리인 만큼 기본적인 트리의 풀이 방법인

DFS, BFS..등을 사용해서 리프노드에 도착했을 경우 최종값을

증가하며 풀어나가면 된다.

 

하지만 문제에서 요구하는 가장 중요한 포인트의 첫 번째는

부모 노드와 자식 노드, 둘 다 하나씩 존재할 때

자식 노드를 삭제하면 부모 노드가 리프 노드가 된다는 것이다.

 

두 번째로 문제에서 어디에도 이진트리라는 단어와 루트노드가 0이라는 말이 없다.

문제의 예시가 이진 트리로 되어있기 때문에 주의해야 하며, 루트 노드를 설정하는

-1이 항상 맨앞에 오는 것도 아니다. 예를 들어 4, 4, 4, 4, -1 의 노드 정보가 주어진다면

루트 노드는 4이며 4를 이루는 자식 노드들은 0, 1, 2 ,3이 된다.

 

이러한 점들을 잘 고려해서 문제를 풀어나가면 구하고자 하는 값을 쉽게 얻을 수 있다.

 

1. 노드의 정보를 저장한다.

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

		int p_node;
		cin >> p_node;

		if (p_node == -1) root = i;
		else parent[p_node].push_back(i);
	}

 

2. 삭제할 노드를 방문하지 않기 위해 방문표시를 진행한다.

	cin >> d_node;
	visited[d_node] = true;

 

3. 삭제 노드가 루트 노드일 경우, 부모와 자식 노드가 하나 씩 있을 경우의 예외처리를 진행해주며 탐색한다.

void dfs(int start)
{
	if (visited[start]) return;

	visited[start] = true;

	if (!parent[start].size() || (parent[start].size() == 1 && parent[start][0] == d_node))
	{
		ans++;
		return;
	}

	for (int i = 0; i < parent[start].size(); i++) 
	{
		if (!visited[parent[start][i]]) 
		{
			dfs(parent[start][i]);
		}
	}
}

 

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>
#include <limits.h>
#include <cstdio>
#include <map>

using namespace std;

vector<int> parent[51];
bool visited[51];
int d_node, ans = 0;

void dfs(int start)
{
	if (visited[start]) return;

	visited[start] = true;

	if (!parent[start].size() || (parent[start].size() == 1 && parent[start][0] == d_node))
	{
		ans++;
		return;
	}

	for (int i = 0; i < parent[start].size(); i++) 
	{
		if (!visited[parent[start][i]]) 
		{
			dfs(parent[start][i]);
		}
	}
}

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

	int N, root;
	cin >> N;

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

		int p_node;
		cin >> p_node;

		if (p_node == -1) root = i;
		else parent[p_node].push_back(i);
	}

	cin >> d_node;
	visited[d_node] = true;

	dfs(root);

	cout << ans;
}