문제

문제 링크

해설

• 항상 머릿속에 ‘트리도 그래프의 한 종류다’ 라고 넣어두면 좋습니다.
• 우선 루트노드의 부모도의 번호가 -1이고, 인덱스 번호가 음수인건 좋지 않으므로 입력받는 모든 부모노드에 1을 더해 입력받았습니다.
  • 따라서 루트노드는 1번노드이며, 0번노드라는 눈에보이지 않는 가상의 노드를 부모노드를 가집니다.
  • 그리고 저희는 리프노드를 찾기 위해 0번노드부터 DFS를 시작할 것입니다.
• 입력받는 정보도 의미부여를 잘 해야 합니다.
  • -1 0 0 1 1이라고 입력을 받았다면, 1씩 더해져 0, 1, 1, 2, 2로 해석이 됩니다.
    • tree[0]: 1
    • tree[1]: 2, 3
    • tree[2]: 4, 5
    • tree[3]:
    • tree[4]:
    • tree[5]:
  • 위와 같이 저장이 될 것이며 지울 노드 ‘2’를 입력받았으니 ‘3’번 노드를 지우면
    • tree[0]: 1
    • tree[1]: 2
    • tree[2]: 4, 5
    • tree[3]:
    • tree[4]:
    • tree[5]:
  • 결국 1->2->4와 1->2->5 밖에 남지 않으므로 리프노드는 2개만 남게 됩니다.
  • 즉, 순회하면서 지울 노드에 대한 정보를 모두 지우면 됩니다.

코드

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

vector<vector<int>> tree;

int dfs(int node) {
	if (node != 0 && tree[node].empty()) return 1;

	int ret = 0;
	for (auto i : tree[node]) ret += dfs(i);

	return ret;
}

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	int N;
	cin >> N;

	tree.resize(N + 1);
	for (int node = 1; node <= N; node++) {
		int parent;
		cin >> parent;
		// 루트노드의 부모노드가 '-1'이므로 루트노드가 1번부터 시작되도록 합니다.
		tree[parent + 1].push_back(node);
	}
	int del_node;
	cin >> del_node;
	// 삭제할 노드와 관련 정보를 모두 삭제합니다.
	while (!tree[del_node + 1].empty()) tree[del_node + 1].pop_back();
	for (auto& node : tree) {
		auto itr = find(begin(node), end(node), del_node + 1);
		if (itr != end(node)) node.erase(itr);
	}
	// 리프노드 개수를 DFS를 이용해서 카운트 합니다.
	int answer = dfs(0);
	cout << answer << '\n';

	return 0;
}

소스코드 링크

결과