[백준][C++] 2263 트리의 순회

www.acmicpc.net/problem/2263

2263번: 트리의 순회

 

 

 

알고리즘 종류

    - 트리

 

 

사고 과정

    - 떠오르는 아이디어가 몇 가지 있었지만, 활용할 수 없음을 알고 검색을 했다. 이 블로그와 이 블로그의 도움으로 해결할 수 있었다. 최종적으로 이 블로그를 보고 깨달았다. 그림으로 설명을 잘 해주셨다.

 

    - 방법을 노트에 적어서 설명하는 것이 편해서 이미지를 첨부했다.

 

 

 

구현(C++)

#include <iostream>
 
using namespace std;
 
int n;
int postOrder[100001];
int inOrder[100001];
int indexes[100001];
 
 
void divideAndConquer(int inStart, int inEnd, int postStart, int postEnd){
    // 분할정복 기법으로 index들이 교차하면 멈춘다.  
    if(inStart > inEnd || postStart > postEnd) return;
    cout << postOrder[postEnd] << " ";
    
    // root의 위치를 찾는다.  
    int rootIndex = indexes[postOrder[postEnd]];
    // root의 위치를 기준으로 좌우에 트리 크기를 알아낸다. 
    int leftSize = rootIndex - inStart;
    int rightSize = inEnd - rootIndex;
    
    // root도 알고, 좌우 트리의 크기도 알게 되었으므로, 다시 분할정복 기법을 적용하여 쭉쭉 내려간다. 
    divideAndConquer(inStart, rootIndex-1, postStart, postStart+leftSize -1);
    divideAndConquer(rootIndex+1, inEnd, postStart+leftSize, postEnd-1);
}
 
 
int main(void){
    
    cin >> n;
    
    for(int i=1; i<=n; i++){
        cin >> inOrder[i];
        // indexex는 중위순회의 값들이 들어온 순서를 기록하는 배열이다.
        // 여기에서 root의 위치를 찾을 것이다.
        // ex) root가 1이면, indexes[1]은 inOrder에서 1의 위치를 알려준다. 
        indexes[inOrder[i]] = i;
    }
    
    for(int i=1; i<=n; i++){
        cin >> postOrder[i];
    }
    
    divideAndConquer(1, n, 1, n);
}

 

 

 

시행착오

    - 간만에 풀어보는 트리 문제에 머리가 어지럽다. 이 문제를 보니, 순회가 주어졌을 때 트리를 만드는 방법도 있을 것 같았다.