BOJ4933: 뉴턴의 사과

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

  • Tree 한정으로 Post-order는 거꾸로 하면 Pre-Order랑 같다.
    • A->B, A->C, B->D, C->D 인 다이아몬드꼴 그래프에서는 다르다.
  • 결국 거꾸로 돌려서 양쪽을 처리하면 된다.
  • 바이너리 트리에서는 각 부모의 자녀 리스트만 있으면 트리의 동치를 비교할 수 있다.
  • 초기화는 항상 조심하자. 초기화된 값이 문제 내에서 의미를 가지면 안된다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <bits/stdc++.h>
using namespace std;


class Graph {
  vector<char> rev;
public:
  unordered_map<char, pair<char, char>> children;
  int input();
  int makeTree(int x);
};

int Graph::input() {
  while(1) {
    string s;
    cin >> s;
    if (s == "end") break;
    else if (s == "nil") rev.push_back(0);
    else rev.push_back(s[0]);
  }
  reverse(rev.begin(), rev.end());
  return rev.size();
}

int Graph::makeTree(int x) {
  int cur = x+1;
  char left = -1, right = -1;
  if(rev[cur]) {
    right = rev[cur];
    cur = makeTree(cur);
  } else cur++;
  if(rev[cur]) {
    left = rev[cur];
    cur = makeTree(cur);
  } else cur++;
  if(left > right) swap(left, right);
  children[rev[x]] = {left, right};
  return cur;
}

int main() {
  ios::sync_with_stdio(false);
  int TC;
  cin >> TC;
  while(TC--) {
    Graph a, b;
    if(a.input() != b.input()) {
      printf("false\n");
      continue;
    }
    a.makeTree(0);
    b.makeTree(0);
    int flag = true;
    for(char c = 'A'; c <= 'Z'; c++)
      if(a.children[c] != b.children[c])
        flag = false;
    printf(flag ? "true\n" : "false\n");
  }
}