[백준/C++] #2263 트리의 순회 (divide and conquer)

문제

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

 

구상

트리의 전위, 중위, 후위 순회와 관련한 문제였는데, 1년 전에 자료구조를 배웠던게 가물가물해서 다시 찾아서 공부해보았다. 아래 포스팅에 너무 잘 나와있어 풀이에 도움이 되었다. 

https://ldgeao99.tistory.com/402

챕터7-2. 트리 | 순회방법(전위, 중위, 후위)

 

우선, 세가지 순회의 특성에 대해 간략히 말해보자면, 

전위 순회는(Preorder) 루트 -> 왼쪽 서브트리 -> 오른쪽 서브트리

중위 순회는(Inorder) 왼쪽 서브트리 -> 루트 -> 오른쪽 서브트리

후위 순회는(Postorder) 왼쪽 서브트리 -> 오른쪽 서브트리 -> 루트

순서로 접근한다. 

 

해당 문제는 중위 순회와 후위 순회를 통해 전위 순회를 알아내는 것이었기 때문에 각각의 특성을 이용하여 재귀로 풀 필요가 있었다. 후위 순회의 마지막 요소는 항상 루트이고, 중위 순회는 루트의 위치를 통해 왼쪽 서브트리와 오른쪽 서브트리로 분할할 수 있다. 해당 특성을 이용하여 후위 순회로 루트 찾고 중위 순회로 분할하고, 파악했던 루트를 가지고 전위 순회를 구성하는 로직을 재귀적으로 반복함으로써 트리의 구조를 파악한 뒤 전위 순회를 구할 수 있었다. 

 

여기서 후위 순회에서 찾은  루트값을 가지고 중위 순회에 존재하는 루트의 위치(인덱스)를 알아내야 했는데, 이때 c++의 unordered map, 즉 파이썬의 dictionary를 사용하여 값을 통해 인덱스를 찾을 수 있도록 했다. 

 

풀이 + 코드

#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_map>
#define endl "\n"
using namespace std;
/*
2263 트리의 순회
*/

int n;
vector<int> inorder, postorder, preorder;
unordered_map<int, int> inorder_index; // 인오더에서 루트의 위치를 빠르게 찾기 위해 인오더 값과 인덱스를 저장한 맵 사용

// 재귀
void build_preorder(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];
    preorder.push_back(root);

    // 인오더에서 루트의 위치 찾기
    int root_index = inorder_index[root];
    int left_tree_size = root_index - in_start;

    // 왼쪽 서브트리 처리 -> 왼쪽 먼저 preorder에 삽입
    build_preorder(in_start, root_index - 1, post_start, post_start + left_tree_size - 1);

    // 오른쪽 서브트리 처리
    build_preorder(root_index + 1, in_end, post_start + left_tree_size, post_end - 1);
}

void solution() {
    inorder.resize(n);
    postorder.resize(n);

    // 인오더 입력
    for (int i = 0; i < n; ++i) {
        cin >> inorder[i];
    }

    // 포스트오더 입력
    for (int i = 0; i < n; ++i) {
        cin >> postorder[i];
    }

    // 인오더 값의 위치를 맵에 저장
    for (int i = 0; i < n; ++i) {
        inorder_index[inorder[i]] = i; // 값 -> 인덱스
    }

    // 프리오더 생성
    build_preorder(0, n - 1, 0, n - 1);

    // 프리오더 출력
    for (int i = 0; i < preorder.size(); ++i) {
        cout << preorder[i] << " ";
    }

}

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    // 입력
    cin >> n; // 이진트리의 정점 개수

    // 로직
    solution();
   
    return 0;

}

 

 

추가로, 전위 순회와 중위 순회가 주어질때, 후위 순회를 도출하는 코드도 작성해보았다. 

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

vector<int> preorder, inorder, postorder;
unordered_map<int, int> inorder_index;

void build_postorder(int pre_start, int pre_end, int in_start, int in_end) {
    if (pre_start > pre_end || in_start > in_end) {
        return;
    }
    
    // 전위 순회의 첫 번째 요소는 루트
    int root = preorder[pre_start];
    
    // 중위 순회에서 루트의 위치 찾기
    int root_index = inorder_index[root];
    int left_tree_size = root_index - in_start;
    
    // 왼쪽 서브트리 처리
    build_postorder(pre_start + 1, pre_start + left_tree_size, in_start, root_index - 1);
    
    // 오른쪽 서브트리 처리
    build_postorder(pre_start + left_tree_size + 1, pre_end, root_index + 1, in_end);
    
    // 후위 순회에서 루트를 방문
    postorder.push_back(root);
}

void solution() {
    preorder.resize(n);
    inorder.resize(n);
    
    // 전위 순회 입력
    for (int i = 0; i < n; ++i) {
        cin >> preorder[i];
    }
    
    // 중위 순회 입력
    for (int i = 0; i < n; ++i) {
        cin >> inorder[i];
    }
    
    // 중위 순회에서 각 값의 위치를 맵에 저장
    for (int i = 0; i < n; ++i) {
        inorder_index[inorder[i]] = i;
    }
    
    // 후위 순회 구하기
    build_postorder(0, n - 1, 0, n - 1);
    
    // 후위 순회 출력
    for (int i = 0; i < postorder.size(); ++i) {
        cout << postorder[i] << " ";
    }
}

int main() {
    // 입력
    int n;
    cin >> n;
    
    // 로직 
    solution();
    
    return 0;
}

 

만일, 전위 순회와 후위 순회를 통해 중위 순회를 찾으려고 한다면, 해가 유일하지 않을 수 있다. 전위 순회와 후위 순회만을 가지고서는 트리의 구조를 완전히 알아낼 수 없기 때문이다.