[ALGOSPOT] 트리 순회 순서 변경 (TRAVERSAL)

출처: algospot.com/judge/problem/read/TRAVERSAL

algospot.com :: TRAVERSAL

<문제>

트리를 순회하는 알고리즘은 트리의 모든 노드들을 특정 순서에 맞춰 방문하지만, 트리는 배열처럼 1차원적인 구조가 아니기 때문에 단 한 가지의 당연한 순서가 존재하지 않습니다. 때문에 필요에 맞춰 순서를 정의해야 합니다. 이진 트리(binary tree)는 모든 노드에 왼쪽과 오른쪽, 최대 두 개의 자손이 있는 트리를 말하는데, 이진 트리의 순회 순서 중 유명한 세 가지로 전위 순회(preorder traverse), 중위 순회(inorder traverse) 그리고 후위 순회(postorder traverse)가 있습니다. 이들은 모두 왼쪽 서브트리를 오른쪽보다 먼저 방문한다는 점에선 같지만, 트리의 루트를 언제 방문하는지가 서로 다릅니다.

전위 순회는 맨 처음에 트리의 루트를 방문하고, 왼쪽과 오른쪽 서브트리를 순서대로 방문합니다. 중위 순회는 왼쪽과 오른쪽 서브트리 사이에 트리의 루트를 방문하고, 후위 순회는 왼쪽과 오른쪽 서브트리를 모두 방문한 뒤에야 루트를 방문합니다.

다음 그림은 이진 트리의 한 예를 보여 줍니다. 이 트리를 전위 순회하면 모든 노드를 27, 16, 9, 12, 54, 36, 72의 순서대로 방문하게 됩니다. 반면 중위 순회했을 때는 9, 12, 16, 27, 36, 54, 72의 순서로, 후위 순회했을 때는 12, 9, 16, 36, 72, 54, 27의 순서로 방문하게 되지요.

어떤 이진 트리를 전위 순회했을 때 노드들의 방문 순서와, 중위 순회했을 때 노드들의 방문 순서가 주어졌다고 합시다. 이 트리를 후위 순회했을 때 각 노드들을 어떤 순서대로 방문하게 될지 계산하는 프로그램을 작성하세요.

 

<입력>

입력의 첫 줄에는 테스트 케이스의 수 C (1≤C≤100)가 주어집니다. 각 테스트 케이스는 세 줄로 구성되며, 첫 줄에는 트리에 포함된 노드의 수 N (1≤N≤100)이 주어집니다. 그 후 두 줄에 각각 트리를 전위 순회했을 때와 중위순회 했을 때의 노드 방문 순서가 N개의 정수로 주어집니다. 각 노드는 1000 이하의 자연수로 번호 매겨져 있으며, 한 트리에서 두 노드의 번호가 같은 일은 없습니다.

 

<출력>

각 테스트 케이스마다, 한 줄에 해당 트리의 후위 순회했을 때 노드들의 방문 순서를 출력합니다.

 

<예제 입력>

2

7

27 16 9 12 54 36 72

9 12 16 27 36 54 72

6

409 479 10 838 150 441

409 10 479 150 838 441

 

<예제 출력>

12 9 16 36 72 54 27

10 150 441 838 479 409

 

 

<아이디어>

프리오더와 인오더를 비교해가면서 포스트오더를 출력하는 문제이다.

 

일단 먼저 각각의 순회 방식의 특징을 살펴보자.

 

프리오더(전위 순회)는 parent -> 왼쪽 자식(서브 트리) -> 오른쪽 자식(서브 트리) 순으로 순회한다.

 

인오더(중위 순회)는 왼쪽 자식(서브 트리) -> parent -> 오른쪽 자식(서브 트리) 순으로 순회한다.

 

포스트오더(후위 순회)는 왼쪽 자식(서브 트리) -> 오른쪽 자식(서브 트리) -> parent 순으로 순회한다.

 

주어진 방식은 프리오더와 인오더인데,

프리오더는 parent부터 출력했으니까 맨 처음에 나온 개체는 root node 일 것이다.

 

그리고 이 root node를 인오더에서 찾으면 root node의 왼쪽 전부는 root node의 왼쪽 자식 서브 트리이고, 오른쪽 전부는 root node의 오른쪽 자식 서브트리이다.

 

인오더 4번 이 root node 였으니까, 1번부터 3번(9, 12, 16)은 왼쪽 서브 트리, 5번부터 7번(36, 54, 72)은 오른쪽 서브트리가 된다.

프리오더를 27에서 한칸 더 가면 왼쪽 서브 트리의 root node 이거나, 오른쪽 서브 트리의 root node 일텐데, 어쨌든 root node 이기 때문에 인오더 1번~3번 혹은 5번~7번 내에 존재하면서, 인오더에서 해당 노드의 왼쪽, 오른쪽은 서브 트리가 된다. 프리오더를 한칸씩 가면서 이 상황을 반복할 수 있다.

 

왼쪽과 오른쪽 범위를 나눴으므로, 재귀적으로 왼쪽으로 갔다가 leaf node 면 출력 후 return, 그리고 오른쪽으로 가서 leaf node 면 출력 후 return, 그리고 parent를 출력하면 최종적으로 포스트 오더를 출력할 수 있다.

 

 

#include <bits/stdc++.h>
using namespace std;
#define swap(a,b) (a)^=(b)^=(a)^=(b)
#define endl '\n'
typedef long long lld;
 
int n;
 
int print_post(int pos, int left, int right,
    vector<int>& preo, vector<int>& ino, map<int, int>& idx)
{
    if(pos == n+1 || left > right) return pos;
    if(left == right)
    {
        cout<<ino[left]<<" ";
        return pos+1;
    }
 
    int parent = idx[preo[pos]], next = print_post(pos+1, left, parent-1, preo, ino, idx);
    int last = print_post(next, parent+1, right, preo, ino, idx);
    cout<<ino[parent]<<" ";
    return last;
}
 
int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int tc;
    cin>>tc;
    while(tc--)
    {
        cin>>n;
        vector<int> preo(n+1, 0), ino(n+1, 0);
        map<int, int> idx;
 
        for(int i=1;i<=n;i++)
            cin>>preo[i];
        for(int i=1;i<=n;i++)
        {
            cin>>ino[i];
            idx[ino[i]] = i;
        }
        print_post(1, 1, n, preo, ino, idx);
        cout<<endl;
    }
    return 0;
}

 

프리 오더의 개체의 인오더에서의 인덱스를 맵으로 저장해서 O(logN) 번만에 찾을 수 있게 했고, 총 N개의 노드를 탐색하니 최종 시간복잡도는 O(NlogN) 임을 알 수 있다.