[BOJ2263] 트리의 순회(분할 정복)

 

---

문제 링크 

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

2263번: 트리의 순회

---

풀이

postorder(후위 순회, 왼쪽-오른쪽 -루트)

- 항상 root가 마지막에 위치(*특징)

- 트리의 특성상 root를 기준으로 왼쪽/오른쪽 서브트리가 나누어지게 때문에 postorder 통해 트리의 root 파악 가능

 

inodrer(중위 순회, 왼쪽-루트-오른쪽)

- root를 기준으로 왼쪽/오른쪽 서브 트리가 나누어진다

- postorder로 구한 root 값으로 inorder의 왼쪽/오른쪽 서브 트리를 분할 할 수 있다

 

분할 정복?

- 큰 문제를 여러 개의 작은 문제로 쪼갠 다음(분할), 

- 작은 문제들의 답을 이용해 큰 문제의 답을 구하는 방법(정복)

 

분할 정복의 과정 

- 문제의 크기가 크다면 1개 이상의 부분 문제로 분할

- 문제의 크기가 충분히 작다면 직접 해결 

- 부분 문제들의 답을 이용해 전체 문제의 답을 계산

 

 

예시

12

8 4 9 2 5 1 10 6 3 11 7 12  -- inorder(중위 순회)

8 9 4 5 2 10 6 11 12 7 3 1 -- postorder(후위 순회)

 

① postorder에서 root 값을 찾는다

② inorder에서 root값을 기준으로 왼쪽/오른쪽 서브 트리를 나눈다

③ 왼쪽 서브 트리의 길이를 구하여, postorder도 왼쪽/오른쪽 서브 트리를 나눈다

이때 왼쪽/오른쪽 서브 트리를 나누는 행위는 시작점과 끝점 인덱스를 사용하는 것으로 대체한다

 

 

 

---

제출 코드

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

public class Main {
    
    static StringBuilder sb = new StringBuilder();
    static InputProcessor inputProcessor = new InputProcessor();
    static String BLANK = " ";
    
    static int N;
    static int[] IN_ORDER, POST_ORDER, INORDER_IDX;

    public static void main(String[] args) throws IOException {
        input();
        pro();
        output();
    }

    private static void input() {
        N = inputProcessor.nextInt();

        IN_ORDER = new int[N + 1];
        POST_ORDER = new int[N + 1];

        for(int i = 1; i <= N; i++) {
            IN_ORDER[i] = inputProcessor.nextInt();
        }

        for(int i = 1; i <= N; i++) {
            POST_ORDER[i] = inputProcessor.nextInt();
        }

        INORDER_IDX = new int[N + 1];
        for(int i = 1; i <= N; i++) {
            INORDER_IDX[IN_ORDER[i]] = i;
        }
    }

    private static void pro() {
        divide(1, N, 1, N); // 분할 정복
    }

    private static void divide(int inS, int inE, int poS, int poE) {
        if(inE < 1 || inE < inS || poE < 1 || poE < poS) return;

        int rootValue = POST_ORDER[poE];
        int rootIndex = INORDER_IDX[rootValue];

        sb.append(rootValue).append(BLANK);

        int len = rootIndex - inS;

        //왼쪽 서브 트리
        divide(inS, rootIndex - 1, poS, poS + len - 1);
        //오른쪽 서브 트리
        divide(rootIndex + 1, inE, poS + len, poE - 1);
    }

    private static void output() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private static class InputProcessor {
        BufferedReader br;
        StringTokenizer st;

        public InputProcessor() {
            this.br = new BufferedReader(new InputStreamReader(System.in));
        }

        public String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }

            return st.nextToken();
        }

        public String nextLine() {
            String input = "";

            try {
                input = br.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }

            return input;
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }
    }
    
}

---

추천 문제

전위/중위 순회가 주어지고, 후위 순회를 구하는 문제

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

4256번: 트리

 

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

6597번: 트리 복구

 

중위 순회(In-Order) 응용하여 문제 풀이

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

2250번: 트리의 높이와 너비

 

 

참고. 

https://loosie.tistory.com/345

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