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

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

1068번: 트리

 

트리와 DFS 문제다.

 

입력으로 받은 부모 노드의 정보를 이용해 루트 노드의 번호를 저장한다.

-1 이외의 값이 들어오면 부모와 자식의 노드를 저장하는데 부모는 유일하기 때문에 부모 노드를 인덱스로 이용했다.

 

지울 노드의 번호를 입력 받고 지울 노드가 루트 노트라면 0을 출력 후 바로 종료한다.

 

단말 노드의 개수를 카운트 하기 위해서는 DFS를 이용한다.

방문 검사 후 단말 노드거나, 자식 노드가 한 개인데 삭제된 노드라면 카운트한다.

그 후 자식 노드의 dfs를 실행한다. 이 때 삭제된 노드에 대해서는 진행하지 않는다.

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

vector <int> v[51];
bool visit[51];
int n, d, root;
int cnt;

void dfs(int index) {
	// 방문한 적이 있으면 return
	if (visit[index]) return;
	// 방문 처리
	visit[index] = 1;

	// 단말 노드거나, 자식 노드가 한 개인데 삭제된 노드라면 카운트
	if (v[index].size() == 0 || (v[index].size() == 1 && v[index][0] == d)) cnt++;

	// 자식 노드 개수만큼 (삭제되지 않은 노드라면) dfs 실행
	for (int i = 0; i < v[index].size(); i++)
		if (v[index][i] != d) dfs(v[index][i]);
}

int main() {
	// 입출력 속도를 단축시키기 위함
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	for (int i = 0; i < n; i++) {
		int a;	cin >> a;
		// -1이 입력되면 루트임을 저장
		if (a == -1) root = i;
		// 그 외의 수가 들어오면 부모와 자식의 관계 저장
		else v[a].push_back(i);
	}

	cin >> d;
	// 루트 노드를 제거하는 경우 예외처리
	if (root == d) {
		cout << 0;
		return 0;
	}

	// 단말 노드 탐색
	dfs(root);
	cout << cnt;
}

(●ˇ∀ˇ●)