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

문제

---

n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다. 이와 같은 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 프로그램을 작성하시오.

 

 

 

풀이

---

다음과 같은 이진그래프가 있다고 가정하고 문제를 풀어보면

그래프

위 In-Order 아래 Pre-Order

노랑 - 부모

빨강 - 왼쪽 자식 트리

파랑 - 오른쪽 자식 트리

으로 하고 설명을 하면,

 

우선 초기의 형태는 위의 그림과 같다.

여기서 Pre-Order 는 왼쪽 자식부터 방문하기 때문에, 왼쪽부터 방문을 하게되면

 

한가지 규칙이 있다는 것을 알 수 있다.

부모는 Post-Order의 가장 뒤라는 점이다.

 

또 여기서 다음 왼쪽 자식으로 가게 된다면,

이제 또 다른  2가지 규칙을 찾을 수 있을 것이다.

 

In-Order의 부모 노드 위치에서 In-Order 시작 ~ 부모노드 - 1 의 개수는 왼쪽 자식 트리의 개수 

부모노드 + 1 ~ In-Order 끝의 개수는 오른쪽 자식트리의 개수

 

이는 Post-Order의 시작 위치 + 왼쪽 자식 트리 개수 + 오른쪽 자식 트리 개수 = 부모노드 위치 가 된다는 것을 알 수 있다.

 

위의 그림처럼 쪼개가면서 찾아가면 된다.

 

이를 이용하여 식을 만들면,

왼쪽 자식

In-Order 시작 = 현재 부모노드의 In-Order의 시작

In-Order 끝 = 현재 부모노드의 위치 - 1

Post-Order 시작 = 현재 Post-Order 시작

Post-Order 끝 = 현재 PostOrder 시작 + 왼쪽 자식 트리 개수(현재 부모노드의 위치 - In-Order 시작 으로 계산 가능) -1

 

오른쪽 자식

In-Order 시작 = 현재 부모노드의 위치 + 1

In-Order 끝 = 현재 부모노드의 In-Order의 끝

Post-Order 시작 = 왼쪽 자식트리 개수(위에서 계산한 방식대로)  + 1

Post-Order 끝 = 현재 Post-Order 끝 - 1 (오른쪽 자식 트리의 가장끝이 때문에)

 

위의 방식으로 재귀를 돌면서 분할정복 하면 된다.

 

 

저는 In-order에서는 위치 정보만 얻기위해 해당 노드의 번호의 위치 인덱스만 저장했습니다.

<전체 코드>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	
	static int N;
	static int[] in_OrderIdx, post_Order, pre_Order;
	static int now;
	
	static StringBuilder sb = new StringBuilder();

	public static int parseInt(String string) {
		return Integer.parseInt(string);
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	
		N = parseInt(br.readLine());
		
		in_OrderIdx = new int[N + 1];
		post_Order = new int[N];
		pre_Order = new int[N];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0 ; i < N ; i++) {
			in_OrderIdx[parseInt(st.nextToken())] = i;
		}
		
		st = new StringTokenizer(br.readLine());
		for(int i = 0 ; i < N ; i++) {
			post_Order[i] = parseInt(st.nextToken());
		}
		
		now = 0;
		getPreOrder(0, N - 1, 0, N - 1);
		
		for(int num : pre_Order) {
			sb.append(num + " " );
		}
		
		System.out.println(sb);
	}
	
	static void getPreOrder(int inStart, int inEnd, int postStart, int postEnd) {
		
		if(inStart > inEnd || postStart > postEnd) { return;}
		
		pre_Order[now++] = post_Order[postEnd];
		
		// 현재 루트의 In-Order에서 위치
		int next = in_OrderIdx[post_Order[postEnd]];
		
		getPreOrder(inStart, next - 1, postStart, postStart + next - inStart - 1 );
		
		getPreOrder(next + 1, inEnd, postStart + next - inStart, postEnd - 1);
	}
}