[BOJ] 백준 1068번 : 트리(C++)

문제

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

문제 풀이

처음에 풀 때 사고 과정은 이러했다.
먼저 입력 받은 부모 노드를 parent[i] 배열에 저장하고 그래프를 만들어 각 노드들의 자식 노드를 저장한다.

삭제하려는 노드를 입력받아 삭제할 노드를 시작 정점으로 하여 BFS를 하였고 삭제할 노드들의 parent에 -2를 저장해 주었다.

그리고 루트 노드(parent[i] = -1) 삭제된 노드(parent[i] = -2)인 노드들을 제외하고 자신을 부모로 하는 노드의 개수를 cnt 배열에 세주었다.

그리고 leaf 노드인지 아닌지 검사를 했는데 루트노드(parent), 삭제된 노드(parent[i] = -2)가 아니고 자식 노드가 0개라면 leaf 노드이다. 여기서 검사할 조건이 하나 더 있다. 바로 루트 노드지만 자식 노드가 없는 경우이다.
루트 노드지만 단일 노드로 존재하면 루트 노드 자체가 leaf 노드이기 때문이다.

답은 맞았지만 풀고 나니 코드가 난잡하다는 생각이 들어 재귀를 통해 수정해 보았다.

처음 구현한 코드

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

int parent[51], cnt[51];
int N, delN, res = 0;
bool visited[51];

vector <int> graph[51];
queue<int> Q;

int main() {

	ios::sync_with_stdio(0);
	cin.tie(0);

	//데이터 N을 입력 받고 0 ~ N - 1까지 각 데이터의 부모 노드를 입력 받는다.
	cin >> N;
	for (int i = 0; i < N; i++) {
		int p;
		cin >> p;
		parent[i] = p;// 부모의 정보를 parent 배열에 저장

		if (p != -1)//자식의 정보를 graph를 통해 저장
			graph[p].push_back(i);
	}

	//삭제하려는 노드를 입력
	cin >> delN;
	Q.push(delN);
	parent[delN] = -2;
	visited[delN] = true;

	while (!Q.empty()) {// BFS를 통해 모든 자손 트리를 삭제한다.(parent[i] == -2로 변경)
		int parentNum = Q.front();
		Q.pop();

		for (int i = 0; i < graph[parentNum].size(); i++) {
			int childNum = graph[parentNum][i];

			if (!visited[childNum]) {
				visited[childNum] = true;
				parent[childNum] = -2;
				Q.push(childNum);
			}
		}
	}

	for (int i = 0; i < N; i++) {// cnt를 통해 자신을 부모로 하는 노드의 개수를 센다
		if (parent[i] != -2 && parent[i] != -1)
			cnt[parent[i]]++;
	}

	for (int i = 0; i < N; i++) { 
		if (parent[i] != -1 && parent[i] != -2 && !cnt[i])
			res++;	//리프 노드면 res++
		else if (parent[i] == -1 && cnt[i] == 0)
			res++;	//루트 노드이지만 리프노드 일 때 res++
	}

	cout << res;

	return 0;
}

재귀로 풀 때 핵심은 루트 노드를 알려주니 그 루트 노드부터 재귀를 통해 트리 순회(=DFS)를 하는 것이다.

순회로 재귀가 진행될 때 삭제된 노드를 탐색하지 못하게 한다.
자신 노드의 자식이 있을 때만 재귀가 진행되므로 재귀가 진행되지 못했다(= 자식이 없으므로 leaf 노드이다.)면 leaf 노드++ 해주는 방식으로 해결할 수 있었다.

재귀로 구현하니 훨씬 간단하고 코드도 직관적이었다.

재귀를 이용한 개선한 코드

#include<iostream>
#include<vector>
#include<queue>

using namespace std;
int N, delN, res = 0, root;

vector <int> graph[51];

void DFS(int parentNum) {

	if (parentNum == delN) //root 노드를 삭제한 경우 바로 종료
		return;

	bool flag = true;	

	for (int i = 0; i < graph[parentNum].size(); i++) {
		int childNum = graph[parentNum][i];		// 자식 노드
		
		if (childNum != delN) {	//삭제할 노드가 아니라면
			flag = false;	//leaf 노드가 아님
			DFS(childNum);	//자식 노드 탐색
		}
	}

	if (flag)	//재귀를 진행하지 않으면(자식이 없다 = leaf이다) res++
		res++;
}

int main() {

	ios::sync_with_stdio(0);
	cin.tie(0);

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

		if (p == -1)	//루트 노드 정보 저장
			root = i;
		else	//그래프 형성
			graph[p].push_back(i);
	}

	cin >> delN; //삭제할 노드 저장
	
	DFS(root);	//root 노드부터 순회

	cout << res;

	return 0;
}