알고리즘 :: 백준 :: 1068 - 트리

 

 

 

❔문제

🔗문제링크

🔄 문제 및 입출력 조건 파악

• 노드 개수 N ≤ 50
• 입력: 0 ~ (N-1)번 노드의 부모 정보, 루트노드는 -1
• 출력: 리프노드의 개수

✏️ 문제풀이

문제에 나와있지 않은 조건을 자신도 모르게 '당연히 그러겠지~'라고 생각하고 풀지 않기를 연습하기 좋은 문제입니다.
(비슷한 문제로 2468 :: 안전영역이 있습니다.)

 

문제 어디에도 주어지는 노드가 '이진 트리'라는 정보가 없습니다.
예시로 주어지는 그림이 이진트리라 햇갈리기 정말 좋습니다.

 

정말로 트리를 구현할 필요는 없습니다.
각 노드의 부모가 입력되므로 배열의 각 칸마다 자식노드의 번호들을 저장하면 됩니다.

• 이때, 앞서 언급했듯이 이진트리가 아니기 때문에 각 칸마다 왼쪽/오른쪽 자식노드의 번호를 저장하기 위해 `std::vector<pair<int, int>>` 타입으로 트리를 정의하시면 안 됩니다.
• `std::vector<vector<int>>`로 연결리스트의 배열로 생각해야 합니다.

예시

9
-1 0 0 2 2 4 4 6 6
4

지우고자 하는 노드 '4'번을 만나면, 진행하지 않는 것을 확인할 수 있습니다.

2
1 -1
0

반드시 0번 노드가 루트노드라는 조건도 없었다는거 알고계시죠?

그리고 만일 못 가는 노드가 있을 때, 단순히 못 가는 걸로 끝나지 않고 1번 노드는 자식노드가 없는거나 마찬가지이므로 리프노드로 취급해줘야 합니다.따라서 위 예제 정답은 1입니다.

 

어떻게 하면 손쉽게 리프노드로 취급할 수 있을까요?
입력받은 (지우려는) 타겟 노드를 아예 트리에서 지워버리면 되지 않을까요?

1. `while (!arr[target].empty()) arr[target].pop_back()`: 해당 인덱스에 들어있는 모든 노드를 pop 해버리기,자식노드와의 연결을 모두 끊어버리기.
2. `arr.erase(find(begin(arr), end(arr), target))`: 트리에서 target 노드를 찾아서 지워버리기.

 

위 두 가지 과정을 거치면, 타겟노드와 연관된 정보가 트리에서 완전히 사라지게 되고,

📝 코드

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

int N, target;
vector<vector<int>> tree;

int dfs(int node) {
	if (node != 0 && tree[node].empty()) return 1;
	int ret = 0;
	for (int i : tree[node]) ret += dfs(i);
	return ret;
}
int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	cin >> N;
	tree.resize(N + 1);
	// 0번 노드를 루트로 하기위해, +1해서 std::vector에 push_back()한다.
	for (int i = 1; i <= N; ++i) {
		int parent;
		cin >> parent;
		tree[parent + 1].push_back(i);
	}
	// 타겟도 증가
	cin >> target;
	target++;
	// 0번~N-1번노드를 순회하며 target에 대한 정보를 모두 지운다.
	while (!tree[target].empty()) tree[target].pop_back();
	for (auto& node : tree) {
		auto itr = find(begin(node), end(node), target);
		if (itr != end(node)) node.erase(itr);
	}
	// 루트 노드(0번 노드)를 시작으로 DFS 순회
	cout << dfs(0);
}

 

🔗 코드 링크

🕧 결과