(C++) - 백준(BOJ) 1068번 : 트리 답

www.acmicpc.net/problem/1068

1068번: 트리

 

트리를 만들고 dfs를 시행하는 문제였습니다.

풀이방법

 

 1. tree를 생성합니다. 자식이 여러개일 경우를 대비해 자식이 추가될 때마다 vector push_back()을 이용합니다.

 2. root node부터 dfs를 시행합니다.

  지울 노드를 방문처리하게 되면 그 이하 자식들도 dfs를 하지않게 가능합니다.

  2-1. 자식노드가 존재한다면 그 자식노드를 다음 dfs 호출의 인자로 넘겨줍니다.

  2-2. 자식노드가 없어 dfs를 호출하지 않게 된다면 leaf 노드이므로 정점을 답에 추가해줍니다.

 

Code

#include <bits/stdc++.h>
using namespace std;

int n, deleteNodeNum;
vector<int> tree[50];
int visited[50];
int parent;
int root = 0;
int ans = 0;
void dfs(int x) {
	if (visited[x]) return;
	visited[x] = 1;
	bool isLeaf = true;
	for (int i = 0; i < tree[x].size(); i++) {
		int next = tree[x][i];
		if (!visited[next]) {
			dfs(next);
			isLeaf = false; 
		}
	}
	if (isLeaf) ans++;
}

int main(){
	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> parent;
		if (parent == -1) root = i;
		else tree[parent].push_back(i);
	}
	cin >> deleteNodeNum;
	visited[deleteNodeNum] = true;
	dfs(root);
	cout << ans << "\n";
}

Test Case

몇 가지 테스트 케이스를 추가해보았습니다.

 

1. 루트와 자식노드 1개씩 있는 2개의 노드로 구성된 트리에서 자식만 지울경우
2
-1 0
1

답 : 1

2. 루트와 자식노드 1개씩 있는 2개의 노드로 구성된 트리에서 부모만 지울경우 

2
-1 0
0

답 : 0