ps
[백준] 4933 - 뉴턴의 사과
kariskan
2022. 9. 13. 21:57
https://www.acmicpc.net/problem/4933
4933번: 뉴턴의 사과
각 테스트 케이스에 대해서, 두 트리가 동등하면 true를, 아니면 false를 출력한다.
www.acmicpc.net
두 개의 트리의 입력이 주어지고, 트리가 동등한 지를 판단하는 문제이다.
입력이 특이하게 들어온다.
따라서 이 입력을 통해서 트리의 구조를 나타내야 한다.
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";
}
}