[백준 1068/C++] 트리

이진중·2022년 5월 26일

DFS 리프노드 트리

알고리즘

목록 보기

30/76

트리

문제

트리에서 리프 노드란, 자식의 개수가 0인 노드를 말한다.

트리가 주어졌을 때, 노드 하나를 지울 것이다. 그 때, 남은 트리에서 리프 노드의 개수를 구하는 프로그램을 작성하시오. 노드를 지우면 그 노드와 노드의 모든 자손이 트리에서 제거된다.

틀린 풀이

입력을 바탕으로 트리를 구현한다. (여기서는 벡터기반으로 구현했다.)
0번 노드부터 dfs나 bfs으로 탐색해서, 제거된 노드가 탐색될때 그 노드를 탐색하지 않고, 뒤로 돌아간다.
리프노드 탐지는 벡터의 크기가 1인경우(연결된 노드가 오직 부모일 경우에만) ans++

반례찾기

풀이중 2가지 실수를 했다.
1. root 노드가 무조건 0번노드인 것으로 고정하여 풀면 안된다.
2. 이경우 백터의 크기가 1인경우만 리프노드가 아니다.

7
3 6 6 -1 0 6 3
4

반례이다. 이렇게 됬을때 4번노드가 삭제되도 0번노드의 백터크기는 2이다.
dfs탐색중 탐색에 끝에 마지막노드에서 +1씩 해가야한다.

올바른 풀이

동일
입력된 root로 부터 dfs나 bfs로 탐색을 해서, 제거된 노드가 탐색될때, 그 노드의 자식들을 부모노드로 옮긴다.
child변수로 자식이 없을경우 리프노드로 인식한다.

실제 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <math.h>
#include <string>
#include <string.h>
#include <queue>

using namespace std;
#define endl "\n"

#define MAX 50+1
int n, cut;
vector<int> adj[MAX];
int root;
int ans;

void dfs(int v) {
	bool leaf = true;
	for (auto ch : adj[v]) {
		if (ch==cut)
		{
			continue;
		}
		else {
			leaf = false;
			dfs(ch);
		}
	}
	
	if (leaf)
	{
		ans++;
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	//ifstream cin; cin.open("input.txt");

	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int parent;
		cin >> parent;
		if (parent == -1)
		{
			root = i;
		}
		else {
			adj[parent].push_back(i);
		}
	}
    
	cin >> cut;
	if (cut==root)
	{
		cout << 0;
	}
	else {
		dfs(root);
		cout << ans;
	}
}

다른사람의 코드

코딩은 확실히 다른사람의 코드를 볼수록 실력이 는다.
여러 사람의 코드를 봐야, 많은 코드를 보고 그 중 어떤 코드가 깔끔하고, 이렇게 코딩하면되는구나를 알수 있다.
코드를 보면 성격이 보인다.
생략을 좋아하는지, 구체적인 시각적 표현을 중시하는지,
MAX값 등을 써서 하드코딩된 부분을 최대한 줄이는지, 그냥 간단하게 숫자를 직접대입하는지 등