BOJ 22856 | 트리 순회

중위 순회에 대해 물어보는 문제다. 이진 트리에서 중위 순회는 left -> parent -> right 순서로 탐색하는 방법이다.

문제에서는 일반적인 중위 순회가 아닌 유사 중위 순회에서의 이동 횟수를 물어보고 있다.

유사 중위 순회는 다음과 같이 진행된다.

일반적인 중위 순회와 같이 진행하는데 모든 이동을 체크해서 개수를 세야 한다.

그러므로 가장 떠올리기 쉬운 방법은 말 그대로 중위 순회의 끝 노드를 체크하고, 이동 횟수를 세면서 탐색하다가 그 노드에 도달하면 이동 횟수 세기를 중지하는 것이다.

단순 구현으로 충분히 풀리는 트리 문제였다.

코드

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

#ifdef LOCAL
constexpr bool local = true;
#else
constexpr bool local = false;
#endif

#define FASTIO ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define ll long long

#define debug if constexpr (local) std::cout
#define endl '\n'

struct Node{
	int left;
	int right;
};

vector<Node> tree;
int cnt, endNode;
int flag = 0;

void realin(int N){
	if (tree[N].left != -1) {
		realin(tree[N].left);
	}
	endNode = N;
	if (tree[N].right != -1){
		realin(tree[N].right);
	}
}

void fakein(int N){
	if (tree[N].left != -1){
		cnt++;
		fakein(tree[N].left);
		if (!flag) cnt++;
	}
	
	if (N == endNode) flag++;
	
	if (tree[N].right != -1){
		cnt++;
		fakein(tree[N].right);
		if (!flag) cnt++;
	}
}


int main(){
	tree.resize(100005);
	int N; cin >> N;
	for (int i = 0; i < N; i++){
		int root, left, right; cin >> root >> left >> right;
		tree[root].left = left;
		tree[root].right = right;
		
		if (tree[left].left == 0 && tree[left].right == 0) tree[left] = {-1, -1};
		if (tree[right].left == 0 && tree[right].right == 0) tree[right] = {-1, -1};
	}
	
	realin(1);
	fakein(1);
	cout << cnt;
}