트리의 순회 2263번 [백준]

이번 문제는 꽤 머리가 깨졌습니다. 저는 Recursion와 Devide and Conquer(분할 정복기법)을 사용하여 풀었습니다. 제가 풀었던, 이런 류의 문제들중 제일 어려웠던거 같습니다.

문제의 규칙을 찾는게 저는 제일 어려웠습니다. 왼쪽으로 가는 경우와 오른쪽으로 가는 경우의 범위값을 inorder postorder에 대해 각각 나눠서 계산을 하였습니다. inorder의 범위는 postorder에서 구한 root(subroot)로 구해내어, root의 index값을 알아낼 수 있습니다. 저는 이렇게 하여 4가지 경우의 범위를 구해내었습니다.

1.왼쪽 subtree로 가는 경우의 inorder tree의 범위값: (instart, root_idx - 1) 시작지점은 그대로 두고, 끝지점은 root_idx-1로 넣었습니다.

 

2.왼쪽 subtree로 가는 경우의 postorder tree의 범위값: postorder의 시작지점은 역시 왼쪽 subtree로 가는 경우이므로 그대로 두어도 괜찮으나, 끝지점은 달라져야 했습니다. 저는 여기서 많이 햇갈렸고, 해결책은 위의 inorder tree의 범위와 같은 수의 범위를 갖어야 되는 것에서 찾았습니다. 따라서 postorder의 끝지점은 시작지점 + (inordertree의 범위 개수).

 

3.오른쪽 subtree로 가는 경우의 inorder tree의 범위값: 시작지점은 root_idx + 1로 했고, 끝지점은 그대로 적용했습니다.

 

4.오른쪽 subtree로 가는 경우의 postorder tree의 범위값: 이번에는 postorder의 끝지점이 기준이 됩니다. 기존 postorder의 root_node에서 오른쪽 subtree의 root_node는 -1만 해주면 되기 때문입니다. 따라서 끝지점은 기존값에서 -1을 하였고, 시작 지점은 역시 동일하게 끝지점에서 inorder범위의 개수만큼 갖게 해주시면 됩니다.

 

전체코드는 다음과 같습니다.

#import<bits/stdc++.h>

using namespace std;

#define fast_io ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

int n;
vector<int> inorder,postorder;
void recursive(int instart,int inend,int poststart,int postend){
    if(instart > inend || poststart > postend)return;
    cout<<postorder[postend]<< " ";// it is root
    int root_idx =0;
    while(inorder[root_idx] != postorder[postend])root_idx++;//find a root_idx in inorder
    recursive(instart,root_idx-1,poststart,poststart +root_idx - instart - 1);
    recursive(root_idx+1,inend,postend - inend + root_idx,postend-1);
}
void solve(){
    cin>>n;
    inorder = vector<int>(n);
    postorder = vector<int>(n);
    for(int &x:inorder)cin>>x;
    for(int &x:postorder)cin>>x;
    recursive(0,n-1,0,n-1);
}
int main() {
    fast_io;
    solve();
    return 0;
}

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