[백준] 4256번 : 트리 Gold2(골드2) - JAVA[자바]

[Gold II] 트리 - 4256

문제 링크

성능 요약

메모리: 37252 KB, 시간: 304 ms

분류

분할 정복, 재귀, 트리

제출 일자

2024년 1월 22일 22:45:38

문제 설명

이진 트리는 매우 중요한 기본 자료 구조이다. 아래 그림은 루트 노드가 유일한 이진 트리이다. 모든 노드는 최대 2개의 자식 노드를 가질 수 있으며, 왼쪽 자식이 순서가 먼저이다. 노드 n개로 이루어진 이진 트리를 BT라고 하자. BT의 노드는 1부터 n까지 유일한 번호가 매겨져 있다.

아래 그림에 나와있는 BT의 루트는 3번 노드이다. 1번 노드는 오른쪽 자식만 가지고 있고, 4와 7은 왼쪽 자식만 가지고 있다. 3과 6은 왼쪽과 오른쪽 자식을 모두 가지고 있다. 나머지 노드는 모두 자식이 없으며, 이러한 노드는 리프 노드라고 부른다.

BT의 모든 노드를 순회하는 방법은 전위 순회(preorder), 중위 순회(inorder), 후위 순회(postorder)로 총 세 가지가 있다. 이 세 방법은 아래에 C 스타일의 의사 코드로 나와 있다. BT의 노드 v에 대해서, v.left는 왼쪽 자식, v.right는 오른쪽 자식을 나타낸다. v가 왼쪽 자식이 없으면 v.left는 ∅와 같고, 오른쪽 자식이 없으면 v.right는 ∅와 같다.

BT를 전위 순회, 중위 순회한 결과가 주어진다. 즉, 위의 함수 중 preorder(root node of BT)와 inorder(root node of BT)를 호출해서 만든 리스트가 주어진다. 두 순회한 결과를 가지고 다시 BT를 만들 수 있다. BT의 전위, 중위 순회한 결과가 주어졌을 때, 후위 순회했을 때의 결과를 구하는 프로그램을 작성하시오.

예를 들어, 위의 그림을 전위 순회하면 3,6,5,4,8,7,1,2, 중위 순회하면 5,6,8,4,3,1,2,7이 된다. 이를 이용해 후위 순회하면 5,8,4,6,2,1,7,3이 된다.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 노드의 개수 n이 주어진다. (1 ≤ n ≤ 1,000) BT의 모든 노드에는 1부터 n까지 서로 다른 번호가 매겨져 있다. 다음 줄에는 BT를 전위 순회한 결과, 그 다음 줄에는 중위 순회한 결과가 주어진다. 항상 두 순회 결과로 유일한 이진 트리가 만들어지는 경우만 입력으로 주어진다.

출력

각 테스트 케이스마다 후위 순회한 결과를 출력 한다.

 

접근 방법

1. PreOrder(VLR)배열은 가장 첫번째가 루트 노드이고 PreOrder 배열에서 루트 바로 다음 노드는 왼쪽 자식 노드를 뜻한다.

2. InOrder(LVR)배열은 은 시작 인덱스부터 루트 노드까지 왼쪽 집합을 뜻한다.

3. 그렇다면 오른쪽 자식은 InOrder 시작 인덱스부터 루트노드까지의 개수를 넘어간다면 오른쪽 자식 노드를 찾을 수 있다.

4. 정답은 후위 순회값이기 때문에 왼쪽 집합(L)을 호출하고 오른쪽 집합(R)을 호출하고 현재 V를 호출한다면 정답을 찾을 수 있다.

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

public class Main {
    static int[] pre, in;
    static StringBuilder sb;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());
        for (int tc = 1; tc <= T; tc++) {
            int n = Integer.parseInt(br.readLine());
            // 전위 순회를 저장하기 위한 배열
            pre = new int[n];
            // 후위 순회를 저장하기 위한 배열
            in = new int[n];
            StringTokenizer st = new StringTokenizer(br.readLine());
            // 전위 순회 저장
            for (int i = 0; i < n; i++) {
                pre[i] = Integer.parseInt(st.nextToken());
            }
            // 중위순회 저장
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < n; i++) {
                in[i] = Integer.parseInt(st.nextToken());
            }
            // 후위순회 호출
            postOrder(0,0,n);
            sb.append("\n");
        }
        System.out.println(sb);
    }

    // 후위 순회 (LRV)
    // 시작 인덱스부터 종료 인덱스는 현재 찾을 수 있는 범위를 뜻한다.
    // 전위순회(pre) 배열에서 찾은 루트노드를 중위순회(In)에서 찾아줘야한다.
    private static void postOrder(int r,int start, int end) {
        for (int i = start; i < end; i++) {
            // Root 값을 발견.
            if(pre[r] == in[i]){
                // 왼쪽 부분(L) 집합을 호출한다.
                // 왼쪽 자식 노드는 루트노드의 바로 다음 인덱스 노드(전위순회는 VLR 순서기때문)
                postOrder(r + 1, start, i);
                // 오른쪽 부분(R) 집합을 호출한다.
                // 루트인덱스에서 In오더에 왼쪽 집합 노드의 개수를 더해야 오른쪽 자식 노드를 찾을 수 있다.
                postOrder(r + i - start + 1, i + 1, end);
                // 현재 Value 값을 넣는다.
                sb.append(pre[r]).append(" ");
                return;
            }
        }
    }
}

 

다른 접근 방법

1. PreOrder(전위순회, VLR)을 통해서는 루트 노드를 구할 수 있다.

2. InOrder(중위순회, LVR)을 통해서 루트노드를 기준으로 한 왼쪽 트리의 집합과 오른쪽트리의 집합을 구할 수 있다.

3. 먼저 루트를 찾는다. -> 프리오더의 첫번째 값

4. 인오더에서 포스트오더에서 구한 루트인덱스로 왼쪽 트리와 오른쪽 트리를 알아낸다.

5. 각 트리의 루트를 찾아서 재귀 호출을 하면 된다.

-> 위에서 한 방법보다 오히려 이게 더 쉽고 이해가 잘된다.

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

public class Main {
    static StringBuilder sb;
    static int[] pre, in;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());
        for (int tc = 1; tc <= T; tc++) {
            int n = Integer.parseInt(br.readLine());
            // 전위 순회
            pre = new int[n];
            // 중위 순회
            in = new int[n];
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int i = 0; i < n; i++) {
                pre[i] = Integer.parseInt(st.nextToken());
            }
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < n; i++) {
                in[i] = Integer.parseInt(st.nextToken());
            }
            postOrder(0,n-1,0,n-1);

            sb.append("\n");
        }
        System.out.println(sb);
    }

    // 후위 순회
    private static void postOrder(int ps, int pe, int is, int ie) {
        // Start가 End보다 클 수 없음.
        if (ps > pe || is > ie) {
            return;
        }

        int rootIdx = 0;
        for (int i = is; i <= ie; i++) {
            // inOrder에서 로트 노드의 인덱스를 찾아냄
            if (pre[ps] == in[i]) {
                rootIdx = i;
                break;
            }
        }
        // 왼쪽 먼저 호출해줘야한다.
        postOrder(ps + 1, ps + (rootIdx - is), is, rootIdx - 1);
        // 오른쪽 호출
        postOrder(ps + (rootIdx - is + 1), pe, rootIdx + 1, ie);
        sb.append(in[rootIdx]).append(" ");
    }
}