[백준] 2263번 트리의 순회

문제

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

풀이과정

트리의 순회 과정을 정확히 숙지하고 있어야 풀 수 있는 문제다.

문제의 입력으로 인오더와 포스트오더가 주어지는데 출력으로 프리오더가 나오게 해야한다.

인오더는 (왼쪽)(루트)(오른쪽) 으로 순회하고 포스트오더는 (왼쪽)(오른쪽)(루트)로 순회한다.

잘보면 루트를 구하는 방법으로 포스트오더의 끝을 선택하는 방법이 쉬워보인다.

한시간 반동안 뭔가 답에 근접한 생각을 한 거 같아서 계속 생각하고 구현해봤지만 결국 되지 않아서 답을 찾아봤다.

내가 생각한대로 함수를 하나 만들고 왼쪽, 오른쪽으로 재귀호출을 통해 해결하는 문제였지만 스스로 해결하지는 못했다. 휴…

post_order의 끝을 이용해 루트를 구하고 구한 루트를 in_order에서 찾아 Index를 기준으로 왼쪽 오른쪽의 범위를 다시 나눠 호출하면 된다.

예제를 통해 이해해보면,

4	2	7	5	1	3	6	in_Order
4	7	5	2	6	3	1	post_Order

post_Order의 끝은 root 이므로 1이 root가 된다.

그리고 in_Order는 root 기준 왼쪽, 오른쪽이 정해지므로

4	2	7	5	in_Order
4	7	5	2	post_Order

는 왼쪽이 된다.

이러한 방법으로 in_Order의 범위와 post_Order의 범위를 구해가며 호출하면 된다. 소스코드를 보는게 더 편할 거 같다.

소스코드

#include <iostream>

using namespace std;

#define MAX_N 100001

int n;
int position[MAX_N];
int in_Order[MAX_N];
int post_Order[MAX_N];
int pre_Order[MAX_N];

void solve(int in_start,int in_end,int post_start,int post_end)
{
    if (in_start > in_end || post_start > post_end) return;

    int root = post_Order[post_end]; // root는 항상 post_Order의 끝 값
    cout << root << " ";

    int p = position[root]; // root 값이 있는 곳 Idx 값 저장

    int left = p - in_start;

    solve(in_start,p-1,post_start,post_start+left-1);
    solve(p + 1, in_end, post_start + left, post_end - 1);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;

    for (int i = 0; i < n; i++) cin >> in_Order[i];
    for (int i = 0; i < n; i++) cin >> post_Order[i];

    for (int i = 0; i < n; i++) position[in_Order[i]] = i; // Idx 저장

    solve(0,n-1,0,n-1);

    return 0;
}