[백준] 4933 - 뉴턴의 사과

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

4933번: 뉴턴의 사과

 

두 개의 트리의 입력이 주어지고, 트리가 동등한 지를 판단하는 문제이다.

 

입력이 특이하게 들어온다.

따라서 이 입력을 통해서 트리의 구조를 나타내야 한다.

 

post order 같은 경우에는 왼쪽 서브 트리 -> 오른쪽 서브 트리 -> 루트의 과정으로 탐색한다.

하지만 이 문제에서 트리의 동등 조건은, (왼쪽 서브 트리 == 왼쪽 서브 트리) || (왼쪽 서브 트리 == 오른쪽 서브 트리)

이므로, 입력을 거꾸로 읽어서 pre order 형태로 나타내었다.

 

왼쪽과 오른쪽 서브 트리의 위치만 서로 바뀐 것일 뿐, 트리의 구조는 같다.

이 말은 다시 말해, 어느 쪽 서브 트리인지는 상관없이 부모의 노드가 같으면 동등한 트리라는 뜻이다.

 

따라서 pre order로 변환한 간선들을 이용해서 부모를 찾고, 동등을 비교하였다.

 

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

int parent[2][30];

int go(int i, int idx,  vector<string>& inp, int pre) {
	if (idx >= inp.size()) return 0;
	if (inp[idx] == "nil") return 1;

	parent[i][inp[idx][0] - 'A' + 1] = pre;

	int sub = go(i, idx + 1, inp, inp[idx][0] - 'A' + 1);
	sub += go(i, sub + idx + 1, inp, inp[idx][0] - 'A' + 1);

	return sub + 1;
}

int main() {
	int n; cin >> n;

	while (n--) {

		string s;
		vector<string> inp1, inp2;
		memset(parent, 0, sizeof(parent));

		while (cin >> s, s != "end") {
			inp1.push_back(s);
		}
		reverse(inp1.begin(), inp1.end());

		while (cin >> s, s != "end") {
			inp2.push_back(s);
		}
		reverse(inp2.begin(), inp2.end());

		go(0, 0, inp1, -1);
		go(1, 0, inp2, -1);

		bool ok = true;

		for (int i = 1; i < 30; i++) {
			if (parent[0][i] != parent[1][i]) {
				ok = false;
				break;
			}
		}

		if (ok)cout << "true\n";
		else cout << "false\n";
	}
}