[C/C++] 백준 5639: 이진 검색 트리 (backtrack을 통한 후위순회)

5639: 이진 검색 트리

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

5639번: 이진 검색 트리

 

풀이!!

 

맨 처음에는 괄호를 이용한 후위 표기식 문제와 같이 stack에 넣음으로써 문제를 해결하려고 했지만 그렇게 할 경우 코드가 너무 복잡해지고 구현할 수가 없어 다른 방법을 모색하였다.

 전위 순회의 특성상 루트-왼쪽 자식-오른쪽 자식 순으로 이동하기 때문에 전체의 루트를 하나만 잡았을 때 배열이 루트(1)-왼쪽자식 (n개)-오른쪽 자식(m)개가 된다.

 예를 들어 50 30 24 5 28 45 98 52 60에서 이것을 하나의 배열로 봤을 때 50이 루트, 30에서 45까지 왼쪽 자식, 98에서 60까지가 오른쪽 자식이 된다. 즉 색깔로 나타내면 50 30 24 5 28 45 98 52 60 이 되는 것이다.

 만약 왼쪽 자식으로 재귀적으로 함수가 호출되었다면 다시 이와 같은 방식으로, 30부터 45까지를 하나의 배열로 생각하여 30 24 5 28  45로 생각하면 된다

 

 후위 순회에서는 왼쪽 자식-오른쪽 자식-루트 순으로 이동하기 때문에 재귀적으로 함수를 만들어줌으로써 노드가 하나가 됐을 때 출력하면 되는 것이다. 따라서

 

post_order(왼쪽 자식 범위)

post_order(오른쪽 자식 범위)

cout<<(루트)

 

로 재귀적으로 불러준다면 나름 쉽게 문제해결이 가능하다.

 

 

하나 주의해야할 점은 입력의 개수가 정해져있지 않으므로 ctrl+'D'를 통해 입력이 끝났다는 것을 써주기 위해 

while(cin>>a)

을 사용했다

 

소스코드!

 

#include<iostream>
#include <algorithm>
#include<queue>
#include<tuple>
#include <string.h>
#include <map>
#include<string>
#include <stack>
#include <limits.h>

using namespace std; //모든 식별자가 고유하도록 보장하는 코드 영역
int arr[10001];


void post_order(int start,int end){
  if(start>end)
    return;
  if(start==end){
    cout<<arr[start]<<"\n";
    return;
  }
  
  int i;
  for(i=start+1;i<=end;i++){
    if(arr[i]>arr[start])
      break;  
  }
  
  post_order(start+1,i-1);
  post_order(i,end);
  cout<<arr[start]<<"\n";
}

int main() {  
  ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  int a,i=0,tmp=0;
  while(cin>>a){
    arr[++i]=a;
    if(a>arr[1]&&tmp==0){
      tmp=i;
    }
  }
  post_order(1,i); 
    
}