[BOJ] 백준 2263번 트리의 순회 (Java)

#2263 트리의 순회

난이도 : 골드 3

유형 : 트리 / 분할 정복 

2263번: 트리의 순회

▸ 문제

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

▸ 입력

첫째 줄에 n(1≤n≤100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다.

▸ 출력

첫째 줄에 프리오더를 출력한다.

 

문제 풀이  

preorder, inorder, postorder에 대한 이해를 가진 상태에서 풀이를 해야한다. 세가지의 순회 움직임을 파악한 후 inorder, postorder를 보고 preorder를 구해주면 된다.  각 순회 흐름도 참고

 

각 순회의 root탐색 우선순위를 눈여겨서 봐둬야 한다.

• preorder (전위 순회)의  탐색순서는 root - left - right 순이다.
• inorder (중위 순회)의 탐색순서는  left - root - right 순이다.
• postorder (후위 순회)의 탐색순서는 left - right - root 순이다.

 

구상

주어진 데이터는 inorder와 postorder이다.

1. postorder

postorder는 항상 root가 맨 뒤에있다. 트리의 특성상 root를 기준으로 왼쪽 자식 트리, 오른쪽 자식 트리로 나누어지기 때문에 postorder를 이용해서 현재 트리의 root가 무엇인지 파악할 수 있다.

2. inorder

inorder는 root를 기준으로 왼쪽 자식 트리와 오른쪽 자식 트리가 나누어진다. 그러면 root에 대한 정보만 있으면 왼쪽, 오른쪽 트리를 분할을 할 수 있게 된다. 

3. 분할정복

분할에 필요한 데이터는 모두 나왔다. root를 기점으로 주어진 트리를 분할하면 된다. root의 데이터는 postorder에서 구하고 분할은 inorder 데이터를 기준으로 해주면 된다.

 

 

시뮬레이션

예제로 inorder와 postorder가 주어진 상태에서 preorder을 구해보자. 

12

8 4 9 2 5 1 10 6 3 11 7 12

8 9 4 5 2 10 6 11 12 7 3 1

 

분할과정

1. 현재 트리의 root는 postorder를 통해 구할 수 있다. int root = postorder[트리 길이]
2. 해당 root가 inorder의 몇 번째 인덱스에 속해있는지 알아낸 후 왼쪽, 오른쪽 트리로 분할해준다. int rootIdx = inIdx[root]
3. 각 왼쪽, 오른쪽 트리에도 inorder와 postorder의 정보를 담아서 보내줘야한다. 배열을 직접 쪼개는건 비효율적이므로 index를 보내주면 된다. traversal(inorder 시작, inorder 끝, postorder 시작, postorder끝)

 

이 두 배열 데이터을 가지고 root를 기준으로 왼쪽, 오른쪽 트리를 분할을 해주면된다.

 

root를 기준으로 왼쪽, 오른쪽 트리 분할

 

 

preorder와 postorder을 통해 분할된 구조를 트리 형태로 나타내면 다음과 같다.

 

preorder와 postorder을 통해 알아낸 트리

 

→ 이제 이 트리의 postorder를 구해주면 답은 postorder :1 2 4 8 9 5 3 6 10 7 11 12 이다.

 

풀이 코드 

분할하는 과정에서 root를 구하게 될 때마다 해당 값을 저장한 다음 출력해주면 된다.

import java.io.*;
import java.util.StringTokenizer;

public class Main {

	static int[] inorder, inIdx, postorder;
	static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		int n = Integer.parseInt(br.readLine());
        
		inorder = new int[n+1];
		st = new StringTokenizer(br.readLine());
		for(int i=1; i<n+1; i++) {
			inorder[i] = Integer.parseInt(st.nextToken());
		}
		postorder = new int[n+1];
		st = new StringTokenizer(br.readLine());
		for(int i=1; i<n+1; i++) {
			postorder[i] = Integer.parseInt(st.nextToken());
		}
		
		// inorder 인덱스
		inIdx = new int[n+1];
		for(int i=1; i<n+1; i++) {
			inIdx[inorder[i]] = i;
		}
        
		solve(1,n,1,n);
		System.out.println(sb.toString());
	}
	
	static void solve(int is, int ie, int ps, int pe) {
		if(ie < is || pe < ps) return;
		int root = postorder[pe];
		int rIdx = inIdx[root];
		sb.append(root+" ");
		
		int len = rIdx - is; // left 트리 길이 
		// left 트리 
		solve(is, rIdx-1, ps, ps+len-1);
		// right 트리 
		solve(rIdx+1, ie, ps+len, pe-1);
	}
}