백준 - 2263 트리의 순회 (C++, Cpp)

1. 문제소개

1-1.  요구사항

• 중복이 없는 n개의 정점을 가진 이진트리가 주어짐
• 이 이진트리를 인오더와 포스트오더로 정렬한 결과가 주어짐
• 인오더와 포스트오더를 참고하여 프리오더를 출력

1-2.  입력값과 출력값

//예제 입력
3
1 2 3 // 인오더
1 3 2 // 포스트오더

2 1 3 // 프리오더

• 3개의 정점을 가진 노드의 인오더와 포스트오더가 주어졌으므로, 현재 이진트리가 어떤 상태인지 알 수 있음
• 완성된 이진트리의 모습을 프리오더로 출력하면 됨

1-3.  문제조건

• 첫째 줄에 n(1 <= n <= 100,000)이 주어짐 (정점의 갯수는 100000만개 이하)
• 두번째 줄은 인오더
• 세번째 줄은 포스트오더

2.문제풀이

2-1.  준비물

• (1) inorder와 postorder를 저장할 정적배열

  int N; // 정점의 갯수를 받을 전역 변수
  
  int inorder[100001];  
  int postorder[100001];
  
  // inorder와 postorder가 size가 100,000이하이지만 index를 1부터 사용하기 위해 100001로 할당

• (2) inorder 값의 index를 저장할 정적배열

  int i_index[100001]; // inoder를 분할하면서 문제를 풀어 나갈것이기 때문에
  					   // inorder 값의 인덱스를 저장할 배열

• (3) 분할정복 함수

void make_preorder(int start_in, int end_in, int start_po, int end_po)
{
    if(start_in > end_in || start_po > end_po) 
        return ;
        
    //inorder든 postorder든 뒤의 인덱스가 앞의 인덱스와 같거나 작으면 return;
    
    int root = postorder[end_po]; //postorder의 마지막 인덱스는 항상 루트
    cout << root << " "; //루트를 출력
    int root_index = i_index[root]; //이 루트 값을 기준으로 inorder의 인덱스를 찾음
    int split = root_index - start_in; // split은 루트 인덱스 기준으로 인오더를 분할했을 때, 왼쪽 인오더의 노드 갯수

    make_preorder(start_in, root_index - 1, start_po, start_po + split - 1); //왼쪽 인오더 시작인덱스, 마지막인덱스, 포스트오더 시작인덱스, 마지막인덱스로 왼쪽 분할
    make_preorder(root_index + 1, end_in, start_po + split, end_po -1); //오른쪽도 마찬가지
}

2-2.  사전 개념

ref :&nbsp;https://commons.wikimedia.org/w/index.php?curid=1535668

• 1) inorder
  • 중위 순회라고도 부르며 Left Node -> Root Node -> Right Node 의 방향으로 노드를 순회한다.
  • 순회하는 순서
    • A -> B -> C -> D -> E -> F -> G -> H -> I

• 2) postorder
  • 후위 순회라고도 부르며 Left Node -> Right Node -> Root Node 의 방향으로 노드를 순회한다.
  • 순회하는 순서
    • A -> C -> E -> D -> B -> H -> I -> G -> F
• 3) preorder
  • 전위 순회라고 부르며 Root Node -> Left Node -> Right Node 의 방향으로 노드를 순회한다.
  • 순회하는 순서
    • F -> B -> A -> D -> C -> E -> G -> I -> H

2-3.  핵심 풀이

• 포스트 오더는 반드시 가장 마지막 인덱스에 "루트"가 온다.
  • 즉 포스트 오더의 가장 마지막 인덱스의 "값"을 기준으로 삼아서 문제 풀이를 시작할 수 있다.
• 위 포스트 오더의 "루트" 값이 인오더에 어디에 위치해 있는지 찾는다.
  • 이후, 루트 값을 기준으로 찾은 인오더의 왼쪽과 오른쪽을 재귀로 호출해서 분할 정복으로 문제를 푼다.

• 우리가 출력해야 할 프리오더는 "루트"가 가장 앞에 나오는 순회방법이므로 함수가  호출 될 때마다 "루트"를 출력하는 것을 먼저 선행한다.
• 재귀를 호출할 때, 인오더는 루트가 있는 인덱스를 기준으로 원래 (인오더)배열의 시작 ~ 루트의 인덱스 - 1으로 하나를 나누고 (왼쪽 분할 인오더)
• 루트의 인덱스 + 1 ~ 원래 배열의 끝으로 두개로 분할한다. (오른쪽 분할 인오더)
• 포스트 오더의 경우에는 원래 (포스트오더)배열의 시작인덱스 ~ 시작인덱스 + 왼쪽 분할 인오더의 갯수로 하나를 나누고 (왼쪽 분할 포스트오더)
• 왼쪽 분할 포스트오더 다음 인덱스 ~ 원래 배열의 마지막 인덱스 - 1로 분할한다. (오른쪽 분할 포스트오더)
• 그리고 탈출조건을 만들어 재귀를 종료시키면 문제가 끝이 난다.

3.코드설명

3-1.  입력 받기

    for (int i = 1; i <= N; i++)
    {
        cin >> inorder[i]; //첫째줄에 inorder를 입력받는다.
        i_index[inorder[i]] = i; //동시에 i_index배열의 inorder의 값을 인덱스로, 인덱스를 값으로 넣어준다.
        			//위 배열을 사용하여 루트 값을 찾고 그 값의 inoder 인덱스를 바로 찾아 줄 것이다.
    }
    for (int i = 1; i <= N; i++)
        cin >> postorder[i]; // 둘째줄에 postorder를 입력받는다.

3-2.  make_preorder 함수 (분할 정복 함수)

void make_preorder(int start_in, int end_in, int start_po, int end_po)
{
    if(start_in > end_in || start_po > end_po) //종료조건, inorder든 postorder든 인덱스가 같으면 탈출
        return ;
    int root = postorder[end_po]; //루트는 반드시 포스트오더의 마지막 인덱스
    cout << root << " "; //preorder이므로 루트를 출력
    int root_index = i_index[root]; //해당 루트를 가진 inorder의 인덱스를 구함
    int split = root_index - start_in; //inorder의 루트 인덱스에서 시작 인덱스를 뺀 값을 split으로 저장

    make_preorder(start_in, root_index - 1, start_po, start_po + split - 1);
    //왼쪽분할
    //inorder는 시작~ 루트인덱스 -1, postorder는 시작~ 시작인덱스 + split-1 
    //여기서 split에서 1을 빼는 이유는 시작인덱스 자체가 이미 1개가 있는 것이므로 총 갯수를 구하려면 1을 빼야함
    
    make_preorder(root_index + 1, end_in, start_po + split, end_po -1);
    //오른쪽 분할
    //inorder는 루트인덱스 + 1 ~ 끝까지, postorder는 왼쪽 postorder 다음칸 부터 마지막 인덱스 -1까지
    //postorder의 마지막 인덱스는 이미 위에서 루트로 사용하였음
}

4.전체 소스 코드

#include <iostream>

#define fast ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
using namespace std;

int N;
int inorder[100001];
int postorder[100001];
int i_index[100001];

void make_preorder(int start_in, int end_in, int start_po, int end_po)
{
    if(start_in > end_in || start_po > end_po)
        return ;
    int root = postorder[end_po];
    cout << root << " ";
    int root_index = i_index[root];
    int split = root_index - start_in;

    make_preorder(start_in, root_index - 1, start_po, start_po + split - 1);
    make_preorder(root_index + 1, end_in, start_po + split, end_po -1);
}

int main()
{
    fast;
    cin >> N;

    for (int i = 1; i <= N; i++)
    {
        cin >> inorder[i];
        i_index[inorder[i]] = i;
    }
    for (int i = 1; i <= N; i++)
        cin >> postorder[i];
    make_preorder(1, N, 1, N);

}