1068 트리

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

C++은 이진트리 라이브러리가 따로 없어서 충격

std::set, std::map에서는 red black tree가 있는데 이진트리는 없었다니 몰랐다

맵으로 구현하는 방법과, 벡터를 이용해서 구현하는 방법 중 벡터 구현 방법으로 풀이

1. 문제

---

간단 설명

노드의 개수와

각 노드 순서대로 부모 노드의 번호가 주어진다

이진트리이므로, 부모 노드는 최대 2개의 자식을 가질 수 있음

세번째 줄에서 지울 노드가 주어지는데,

노드가 지워지면 땡겨지는게 아니라 자식 노드까지 통째로 날아감

2. 문제 분석

---

주의점

• 루트 노드는 -1로 주어진다

• 노드 삭제시, 자식 노드들도 통째로 날아간다

알고리즘

1. N을 입력받고 각 노드별 부모 정보를 입력받는다
    1-1. 만약 루트 노드라면 따로 기록해둔다
2. 지울 노드를 입력받는다
    2-1. 만약 루트 노드를 삭제하면 모든 노드가 삭제되므로, 리프 노드도 0이다
3. DFS를 통해 리프 노드의 개수를 확인한다
    3-1. 만약 방문한 노드라면 리턴
    3-2. 리프 노드인 경우(자식 노드가 0개), 리프 노드 개수를 + 1 증가시키고 리턴한다
    3-2. 리프 노드가 아니지만, 자식이 한개이고, 그 자식이 삭제할 노드인 경우 리프 노드로 친다
    3-3. 위 과정을 통과하면 일반 노드이므로 자식들을 탐색한다.
        3-3-1. 삭제할 노드라면 패스
        3-3-2. 아니라면 노드를 따라 더 들어간다

필요변수

• 노드 개수 int N

• 각 노드의 부모 정보를 저장할 연결 리스트 벡터 vector<int> tree[51] (N 최대 50)

• DFS시 노드 방문 체크용 bool vistied[51]

• 루트 노드 번호 int root

• 삭제할 노드 번호 int k

• 리프 노드의 개수를 저장할 int leaf

3. 소스코드

---

#include <iostream>
#include <vector>

using namespace std;

vector<int> tree[51]; // 각 노드의 부모 노드의 정보를 가지는 벡터. 트리를 직접 구현하지 않음
bool visited[51];
int root, k, leaf = 0;

void dfs(int node) {

	// 탈출 조건 1. 이미 방문한 노드
	if (visited[node]) return;

	visited[node] = true;

	// 리프 노드인경우
	if (tree[node].size() == 0) {
		leaf++;
		return;
	}
	// 혹은 자식 개수가 1개인데, 그 자식이 삭제할 노드인 경우
	else if (tree[node].size() == 1 && tree[node][0] == k) {
		leaf++;
		return;
	}

	// 자식들 탐색
	for (int i = 0; i < tree[node].size(); i++) {
		// 삭제할 노드라면 패스
		if (tree[node][i] == k) continue;
		// 아니라면 더 들어가본다
		dfs(tree[node][i]);
	}
}

int main() {
	freopen_s(new FILE*, "input.txt", "r", stdin);
	int N;
	cin >> N;

	for (int i = 0; i < N; i++) {
		int node;  cin >> node;
		if (node == -1) {
			root = i;
		}
		else {
			tree[node].push_back(i); // 노드의 부모 노드를 저장
		}
	}

	cin >> k; // 지울 노드 입력
	// 루트 지우는 경우 다날라감
	if (k == root) {
		cout << 0;
		return 0;
	}

	dfs(root); // k 를 지우면 k와 연결된 모든 노드 정보들도 삭제된다
	cout << leaf;
	return 0;
}

이진 트리 자료구조는 잘 알고 있었지만, 막상 구현하려하니 막막했다.

C++로 구현하는 방법을 더 학습해야겠다