백준 2263번 트리의 순회

문제 링크 : https://www.acmicpc.net/problem/2263

2263번: 트리의 순회

 

문제

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

 

입력

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

 

출력

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

 

풀이

이 문제는 우선 전위, 중위, 후위 순회를 알고있어야 풀 수 있는 문제이다. 알고 있었어도 가끔 헷갈리는데

간단히 설명하자면 "전위 중위 후위"라는 것은 부모를 언제 방문하냐에 따라 달려있다.(전 중 후)

이 문제는 영어로 프리오더, 인오더, 포스트오더라고 설명했는데, pre(전), in(중간), post(이후) 라고 글자 그대로의 의미를 생각해보면 알 수 있을것이다.

• 전위 순회 : 부모 -> 왼쪽 자식 노드 -> 오른쪽 자식 노드
• 중위 순회 : 왼쪽 자식 노드 -> 부모 -> 오른쪽 자식 노드
• 후위 순회 : 왼쪽 자식 노드 -> 부모 -> 오른쪽 자식 노드

그림을 통해 살펴보면

이런 조잡한 트리에 대해서 각각의 순회를 적용시켜보자

• 전위 순회 : 1 2 3 4 5 6 7
• 중위 순회 : 3 2 4 1 6 5 7
• 후위 순회 : 3 4 2 6 7 5 1

이 되는 걸 볼 수 있다.

 

그럼 이제 문제로 넘어가보면

문제에서 주어지는 것은 인오더(중위 순회)와 포스트오더(후위 순회)이다.

이렇게 순회의 결괏값을 주고 트리의 모양 또는 다른 순회의 결괏값을 알아내는 문제에선

전위 순회나 후위 순회가 주어지면 단번에 루트가 무엇인지 파악 가능하다.

여기선 후위 순회가 주어졌고, 후위 순회는 부모를 가장 나중에 방문하므로 부모들의 부모인 루트는 맨 마지막에 찍히는 것을 볼 수 있겠다. 또한 너무나 당연하게도 전위 순회는 루트가 가장 먼저 나온다.

우리는 이 사실을 이용해서 후위 순회에서 루트를 뽑아다가 전위 순회에 차례대로 붙이는 과정을 반복할 것이다.

그렇다면 중위 순회는 왜 주어졌을까? 후위 순회에서 루트를 뽑을 때 어디부터 어디까지가 왼쪽 서브 트리인지를 알고 뽑아야 전위 순회에 차례대로 루트를 붙일 수 있기 때문이다.

그림으로 살펴보자면

후위 순회

후위 순회의 맨 끝(루트)은

중위 순회

중위 순회의 정 가운데이고 이를 기준으로 왼쪽 서브 트리와 오른쪽 서브 트리가 정확히 갈리는 것을 볼 수 있다.

추가로

후위 순회

후위 순회에서도 마찬가지로 중위 순회에서 루트를 기준으로 갈라진 원소 수 만큼 왼쪽과 오른쪽이 정확히 나뉜다는 것을 알 수 있다. 그렇다면 이는 분할 정복과 유사하게 각각의 왼쪽 오른쪽 서브 트리를 위와 같은 방식으로 루트를 찾고, 다시 나누면 된다.

후위 순회

중위 순회

 

소스 코드

#include <iostream>
#include <vector>
using namespace std;
 
int inorder[100001];
int postorder[100001];
int pos[100001];
int 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 = postorder[post_end];
    printf("%d ", root);
    int p = pos[root]; //inorder에서 루트의 위치
    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()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &inorder[i]);
    }
    for (int i = 0; i < n; i++) {
        scanf("%d", &postorder[i]);
    }
    for (int i = 0; i < n; i++) {
        pos[inorder[i]] = i;
    }
    solve(0, n - 1, 0, n - 1);
    return 0;
}

코드 설명

solve 함수가 아까 설명한 과정을 담은 함수이다.

함수의 인자로 인오더의 시작과 끝, 포스트오더의 시작과 끝을 넣었고,

기저 사례로 인오더의 시작이 끝보다 클 경우 또는 포스트오더의 시작이 끝보다 클 경우 바로 리턴시켰다.

결국 문제는 프리오더를 출력하는 것이기 때문에 구하는 모든 루트를 계속 출력시켜주면 이게 프리오더가 된다.

반드시 왼쪽 -> 오른쪽 순으로 함수를 호출해야한다!

개발환경 : Visual Studio 2019

지적, 조언 언제든지 환영입니다~~