[C++]백준 - 2263번 문제

2263번: 트리의 순회 (acmicpc.net)

2263번: 트리의 순회

 

2263번 : 트리의 순회

---

n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다. 이와 같은 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 프로그램을 작성하시오.

 

입력

---

첫째 줄에 n(1≤n≤100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다.

 

 

출력

---

첫째 줄에 프리오더를 출력한다.

 

 

---

 

생각해 볼 점

---

후위 순회와 중위 순회의 결과물을 입력 받은 후, 실제 트리를 찾아내야 합니다.

 

[백준] 2263번 트리의 순회 - C++ - DGOS | 동꿀오소리 (donggoolosori.github.io)

[백준] 2263번 트리의 순회 - C++ - DGOS | 동꿀오소리

위의 링크에서 아주 잘 설명해주고 있습니다.

 

Root, Left, Right를 분할해주면서 맨 아래 Leaf 노드까지 내려갔다면, 트리가 어떻게 생겼는지 확인할 수 있습니다.

 

 

코드

---

#include <iostream>
#include <stack>
using namespace std;

//int 3개 짜리 구조체
struct thr
{
    int in_start;   //중위 순회 시작점
    int post_start;     //후위 순회 시작점
    int len;    //트리의 길이
};

int main() 
{
    int N;
    scanf("%d", &N);
    
    int *in = new int[N];
    int *post = new int[N];
    
    for(int i = 0; i < N; i++) scanf("%d", &in[i]);
    for(int i = 0; i < N; i++) scanf("%d", &post[i]);
    
    thr t;
    t.in_start = 0;
    t.post_start = 0;
    t.len = N;
    
    stack<thr> st;
    st.push(t);            
    while(!st.empty())
    {
        int in_start = st.top().in_start;
        int post_start = st.top().post_start;
        int len = st.top().len;
        
        //트리의 루트는 후위 순회의 가장 마지막 원소
        int root = post[post_start + len - 1];
        st.pop();
        
        //중위 순회에서 root를 찾아 좌, 우의 트리로 나눔
        for(int i = in_start; i < in_start + len; i++)
        {
            if(in[i] == root)
            {
                printf("%d ", root);
                thr left, right;
                
                //좌측 트리
                left.in_start = in_start;
                left.post_start = post_start;
                left.len = i - in_start;

                //우측 트리
                right.in_start = i + 1;
                right.post_start = post_start + left.len;
                right.len = in_start + len - 1 - i;

                //Left를 먼저 탐색해야 전위순회이므로 right부터 push
                if(0 < right.len) st.push(right);
                if(0 < left.len) st.push(left);
            }
        }
    }
    
    delete[] in;
    delete[] post;
	return 0;
}

 

그 외

---

개인적으로 정말 어렵게 생각했던 문제 중 하나입니다.

 

문제의 해결법을 생각하는 것 자체는 가능한데, 정말 그 방법이 맞는지 확신을 갖는 데에 시간이 걸렸던 것 같습니다.