백준1068 - 트리

문제링크 : https://www.acmicpc.net/problem/1068
알고리즘 종류 : DFS
솔? : 답지보고함
핵심 아이디어 : DFS라는 걸 알고, vector 배열에 자식노드를 줄줄이 꿰내고 잘 삭제해내는 아이디어 

#include <bits/stdc++.h>

using namespace std;


int N, erase;
vector<int> tree[51];
int leap_cnt = 0;
int del_node;

void dfs(int idx) {
	bool not_leap = false;
	//다음번 노드를 갔는데 NULL이면 not_leap가 바뀌지 않는다.
	//각 노드에 물려 있는 자식들을 순회한다.
	for (auto next : tree[idx]) {
		not_leap = true;
		//이는 즉 말단 노드라는 뜻이다.
		dfs(next);
	}
	//말단노드임이 맞다면 카운트해준다.
	if (!not_leap) leap_cnt++;
}

void solution() {
	scanf("%d", &N);
	int root = 0;
	for (int i = 0; i < N; i++) {
		int tmp;
		scanf("%d", &tmp);
		//부모가 없는 노드는 루트노드일수밖에없다
		if (tmp == -1) {
			root = i;
			continue;
		}
		//부모 노드에 찾아가서 자식열로 넣어버린다.
		tree[tmp].push_back(i);
	}

	scanf("%d", &del_node);
	//일단 제거할 노드를 죽인다
	tree[del_node].clear();
	// 그리고 삭제된 노드를 자식으로 가진 상위 노드들에서 없애 버린다
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < tree[i].size(); j++) {
			if (del_node == tree[i][j]) tree[i].erase(tree[i].begin()+j);
		}
	}
	if (del_node != root) dfs(root);
	printf("%d", leap_cnt);

}

int main() {
	solution();
	return 0;
}

후기 : 개념을 잘 이해하자...,  auto 문법은 앞으로도 유용하게 쓰일듯하다..

잘설명된 링크 : https://github.com/tony9402/baekjoon/blob/main/solution/tree/1068/main.cpp