[백준 2263] - [분할정복] - 트리의 순회(java)

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

---

이 문제는 좀 변태적인 문제라 확신한다. 

중위 순회(In-order) 가 주어지고 후위 순회(Post-order)가 주어졌을때 전위순회(Pre-order)를 구하라는 문제이다.

예제 입 출력은 아래와 같다.

입력

3
1 2 3
1 3 2

출력

2 1 3

하지만 예제 입출력에는 노드가 3개여서 예제 입출력을 기준으로 풀면 구하기 힘들다.

그래서 예제로 트리하나를 만들었고 전위, 중위, 후위 순회의 값을 먼저 구한뒤 이 값이 나오도록 유도해봤다.

위의 트리를 만들어 보았고 각각 전위, 중위, 후위 순회를 구해봤다.

전위 순회 : 1 -> 2 -> 4 -> 7 -> 8 -> 5 -> 3 -> 6 -> 9 

중위 순회 : 7 -> 4 -> 8 -> 2 -> 5 -> 1 -> 3 -> 9 -> 6

후위 순회 : 7 -> 8 -> 4 -> 5 -> 2 -> 9 -> 6 -> 3 -> 1

이제 이 문제를 어떻게 접근해야 되는지 고민해보자.

계속 그려보면서 해본 결과 신기한 규칙을 찾았다. 

중위 순회

7

4

8

2

5

1

3

9

6

후위 순회

7

8

4

5

2

9

6

3

1

후위 순회의 마지막이 루트이다.

그리고 루트를 기준으로 중위 순회의 왼쪽이 로트의 왼쪽 자식 노드이고 오른쪽이 우측 자식노드들이다.

그럼 루트 1을 기준으로 좌측 자식노드 를 중위순회에서 나누면

중위 순회 기준 루트의 왼쪽 자식노드들

7

4

8

2

5

1

3

9

6

중위 순회 기준 루트의 오른쪽 자식노드들

7

8

4

5

2

9

6

3

1

그리고 잘 보면 중위 순회에서의 루트의 인덱스를 기준으로 후위순회에서 보면 왼쪽이 루트의 자식노드이고

중위순회의 인덱스 포함 해서 후위순회의 루트 인덱스 전까지가 루트의 오른쪽 노드들이다. 

루트 I 를 기준으로  좌측 노드들의 중위, 후위 순회의 시작 종료 인덱스와

루트 I 를 기준으로 우측 노드들의 중위, 후위 순회의 시작 종료 인덱스 를 구하고 자식노드들도 같은 방식으로 구한다면 전위 순회를 구할 수 있다. 

나머지는 소스를 보면서 분석 해보길.. 힘들었다.

소스

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    public static int size;
    
    public static int[] in_order;
    public static int[] in_order_idx; // 중위 순회에 루트들의 인덱스 정보를 입력한다.
    public static int[] post_order;
    
    public static StringBuilder sb;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        size = Integer.parseInt(br.readLine());
        
        in_order = new int[size+1];
        in_order_idx = new int[size+1];
        post_order = new int[size+1];
        
        sb = new StringBuilder();
        
        
        st = new StringTokenizer(br.readLine());
        
        for(int i=1; i <= size; i++) 
            in_order[i] = Integer.parseInt(st.nextToken());
        
        st = new StringTokenizer(br.readLine());
        for(int i=1; i <= size; i++) post_order[i] = Integer.parseInt(st.nextToken());
        
        // 중위순회에 노드들이 루트일경우 인덱스 정보를 저장
        for(int i=1; i <= size; i++) in_order_idx[in_order[i]] = i;
        
        getPreOrder(1, size, 1, size);
        System.out.println(sb.toString());
    }
    
    public static void getPreOrder(int inO_start, int inO_end, int poO_start, int poO_end) {
        // 중위, 후위 준회의 시작점은 종료점 보다 크면 안된다.
        if(inO_start > inO_end || poO_start > poO_end) return;
        
        // 루트를 구한다. 후위 순회의 마지막 인덱스 poO_end가 루트의 인덱스이다. 
        int root = post_order[poO_end];
        sb.append(root + " ");
        
        // 중위 순회에서 루트의 인덱스를 알아온다.
        int rootIdx = in_order_idx[root];
        // 중위 순회에서 루트 기준 왼쪽에 몇개가 있는지 계산한다.
        int left = rootIdx - inO_start;
        
        //좌측 자식 노드들을 구한다. 
        getPreOrder(inO_start, rootIdx-1, poO_start, poO_start+ left-1);
        
        // 우측 자식 노드들을 구한다. 
        getPreOrder(rootIdx+1, inO_end, poO_start + left, poO_end - 1);
    }
}