🚀 [TRAVERSAL] 문제 😊😊😊😊😊
트리를 순회하는 알고리즘은 트리의 모든 노드들을 특정 순서에 맞춰 방문하지만, 트리는 배열처럼 1차원적인 구조가 아니기 때문에 단 한 가지의 당연한 순서가 존재하지 않습니다. 때문에 필요에 맞춰 순서를 정의해야 합니다. 이진 트리(binary tree)는 모든 노드에 왼쪽과 오른쪽, 최대 두 개의 자손이 있는 트리를 말하는데, 이진 트리의 순회 순서 중 유명한 세 가지로 전위 순회(preorder traverse), 중위 순회(inorder traverse) 그리고 후위 순회(postorder traverse)가 있습니다. 이들은 모두 왼쪽 서브트리를 오른쪽보다 먼저 방문한다는 점에선 같지만, 트리의 루트를 언제 방문하는지가 서로 다릅니다.
전위 순회는 맨 처음에 트리의 루트를 방문하고, 왼쪽과 오른쪽 서브트리를 순서대로 방문합니다. 중위 순회는 왼쪽과 오른쪽 서브트리 사이에 트리의 루트를 방문하고, 후위 순회는 왼쪽과 오른쪽 서브트리를 모두 방문한 뒤에야 루트를 방문합니다.
다음 그림은 이진 트리의 한 예를 보여 줍니다. 이 트리를 전위 순회하면 모든 노드를 27, 16, 9, 12, 54, 36, 72의 순서대로 방문하게 됩니다. 반면 중위 순회했을 때는 9, 12, 16, 27, 36, 54, 72의 순서로, 후위 순회했을 때는 12, 9, 16, 36, 72, 54, 27의 순서로 방문하게 되지요.
어떤 이진 트리를 전위 순회했을 때 노드들의 방문 순서와, 중위 순회했을 때 노드들의 방문 순서가 주어졌다고 합시다. 이 트리를 후위 순회했을 때 각 노드들을 어떤 순서대로 방문하게 될지 계산하는 프로그램을 작성하세요.
🔑 [풀이]
트리 순회 방법의 특성을 통해 문제를 해결합니다.
먼저 트리를 순회하는 psedo 코드를 살펴보겠습니다.
// 전위순회
if (currentNode)
{
Visit(currentNode);
Preorder(currentNode->leftChild);
Preorder(currentNode->rightChild);
}
전위 순회는 루트 -> 왼쪽 서브트리 -> 오른쪽 서브트리를 방문합니다.
// 중위순회
if (currentNode)
{
Inorder(currentNode->leftChild);
Visit(currentNode);
Inorder(currentNode->rightChild);
}
중위 순회는 왼쪽 서브트리 -> 루트 -> 오른쪽 서브트리를 방문합니다.
// 후위순회
if (currentNode)
{
Postorder(currentNode->leftChild);
Postorder(currentNode->rightChild);
Visit(currentNode);
}
후위 순회는 왼쪽 서브트리 -> 오른쪽 서브트리 -> 루트를 방문합니다.
트리의 방문 순서는 위의 그림처럼 생각하시면 단순하게 생각하실 수 있습니다.\
위의 내용들을 통해서 왼쪽 서브트리 -> 오른쪽 서브트리 -> 루트를 방문하여 문제를 해결할 수 있습니다.
⌨️ 입력
입력의 첫 줄에는 테스트 케이스의 수 C (1≤C≤100)가 주어집니다. 각 테스트 케이스는 세 줄로 구성되며, 첫 줄에는 트리에 포함된 노드의 수 N (1≤N≤100)이 주어집니다. 그 후 두 줄에 각각 트리를 전위 순회했을 때와 중위순회 했을 때의 노드 방문 순서가 N개의 정수로 주어집니다. 각 노드는 1000 이하의 자연수로 번호 매겨져 있으며, 한 트리에서 두 노드의 번호가 같은 일은 없습니다.
🖥 출력
각 테스트 케이스마다, 한 줄에 해당 트리의 후위 순회했을 때 노드들의 방문 순서를 출력합니다.
🖱 입력 예제
2
7
27 16 9 12 54 36 72
9 12 16 27 36 54 72
6
409 479 10 838 150 441
409 10 479 150 838 441
💻 출력 예제
12 9 16 36 72 54 27
10 150 441 838 479 409
💎 전체 코드는 다음과 같습니다.
//
// TRAVERSAL.cpp
// AALGGO
//
// Created by inhyeok on 2021/12/05.
//
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("TRAVERSAL.txt");
vector<int> slice(const vector<int>& vec, int a, int b){
return vector<int>(vec.begin() + a, vec.begin()+b);
}
void printPostOrder(const vector<int>& preorder, const vector<int>& inorder){
// 트리에 포함된 노드 수
int n = preorder.size();
// 트리가 비었으면
if(preorder.empty()) return;
// root 는 항상 전위 순회의 0번째
const int root = preorder[0];
// find() 몇번째 위치를 리턴한다.
// inorder 에서 루트 위치를 빼준것이 왼쪽 트리의 개수이다.
const int L = find(inorder.begin(), inorder.end(), root) - inorder.begin();
// 오른쪽 트리의 개수
const int R = n - 1 - L ; // n-1 루트를 빼준 트리의 개수
// 왼쪽과 오른쪽 을 순회한 결과
printPostOrder(slice(preorder,1,L+1), slice(inorder,0,L));
printPostOrder(slice(preorder,L+1,n), slice(inorder,L+1,n));
// post는 루트가 마지막이기 때문.
cout << root << " ";
}
int main(){
int test_case;
fin >> test_case;
for(int test=0; test<test_case; test++){
int n;
fin >> n;
vector<int> preorder(n,0);
vector<int> inorder(n,0);
for(int i=0; i<n; i++){
fin >> preorder[i];
}
for(int i=0; i<n; i++){
fin >> inorder[i];
}
printPostOrder(preorder, inorder);
cout << endl;
}
}
Comments