[백준] 9934 완전 이진 트리 (JAVA)

문제 링크:

9934번: 완전 이진 트리

 

 

난이도: 실버 1

 

 

문제:

 

상근이는 슬로베니아의 도시 Donji Andrijevci를 여행하고 있다. 이 도시의 도로는 깊이가 K인 완전 이진 트리를 이루고 있다. 깊이가 K인 완전 이진 트리는 총 2K-1개의 노드로 이루어져 있다. (아래 그림) 각 노드에는 그 곳에 위치한 빌딩의 번호가 붙여져 있다. 또, 가장 마지막 레벨을 제외한 모든 집은 왼쪽 자식과 오른쪽 자식을 갖는다.

깊이가 2와 3인 완전 이진 트리

상근이는 도시에 있는 모든 빌딩에 들어갔고, 들어간 순서대로 번호를 종이에 적어 놓았다. 한국으로 돌아온 상근이는 도시가 어떻게 생겼는지 그림을 그려보려고 하였으나, 정확하게 기억이 나지 않아 실패했다. 하지만, 어떤 순서로 도시를 방문했는지 기억해냈다.

1. 가장 처음에 상근이는 트리의 루트에 있는 빌딩 앞에 서있다.
2. 현재 빌딩의 왼쪽 자식에 있는 빌딩에 아직 들어가지 않았다면, 왼쪽 자식으로 이동한다.
3. 현재 있는 노드가 왼쪽 자식을 가지고 있지 않거나 왼쪽 자식에 있는 빌딩을 이미 들어갔다면, 현재 노드에 있는 빌딩을 들어가고 종이에 번호를 적는다.
4. 현재 빌딩을 이미 들어갔다 온 상태이고, 오른쪽 자식을 가지고 있는 경우에는 오른쪽 자식으로 이동한다.
5. 현재 빌딩과 왼쪽, 오른쪽 자식에 있는 빌딩을 모두 방문했다면, 부모 노드로 이동한다.

왼쪽 그림에 나와있는 마을이라면, 상근이는 2-1-3 순서대로 빌딩을 들어갔을 것이고, 오른쪽 그림의 경우에는 1-6-4-3-5-2-7 순서로 들어갔을 것이다. 상근이가 종이에 적은 순서가 모두 주어졌을 때, 각 레벨에 있는 빌딩의 번호를 구하는 프로그램을 작성하시오.

 

 

입력:

첫째 줄에 K (1 ≤ K ≤ 10)가 주어진다.

둘째 줄에는 상근이가 방문한 빌딩의 번호가 들어간 순서대로 주어진다. 모든 빌딩의 번호는 중복되지 않으며, 구간 [1,2K)에 포함된다.

 

 

문제 이해:

이 문제 이해는 어렵지 않다.

첫 번째 줄에 트리의 높이 K가 주어지고, 두 번째 줄에는 해당 트리를 중위 순회(inorder) 한 결과가 주어진다.
주어진 중위 순회 결과를 바탕으로 트리를 복원하여, 루트 노드부터 하위 레벨까지 레벨별로 출력하는 것이 문제이다.

 

 

구현 방향:

이 문제를 해결하기 위해 처음에는 재귀(recursion) 방식을 떠올렸다.

입력으로 주어진 숫자들의 인덱스를 활용해 답을 구할 수 있을 것이라 생각했지만, 30분가량 고민해도 풀리지 않았다.

 

결국 블로그를 참고하여, 트리의 루트를 찾고 이를 기준으로 왼쪽 서브트리와 오른쪽 서브트리로 재귀적으로 분할하는 방식을 알게 되었고, 그 방법으로 문제를 해결할 수 있었다.

 

즉, 주어진 트리의 높이 K를 통해 전체 노드의 개수를 파악하고, 배열의 중앙(mid) 원소를 루트로 두어 왼쪽 구간은 왼쪽 서브트리, 오른쪽 구간은 오른쪽 서브트리로 두며 재귀적으로 탐색하는 방식이다.

 

이를 코드로 그대로 구현하면 다음과 같다.

 

 

정답코드:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    static int k;
    static int[] nodeArr;
    static List<List<Integer>> levelLists = new ArrayList<>();

    //즁위순회 해결
    public static void inorder(int start, int end, int depth) {
        if (start > end) return;

        int mid = (start + end) / 2; // 중앙이 현재 서브트리의 루트
        levelLists.get(depth).add(nodeArr[mid]);

        inorder(start, mid - 1, depth + 1); // 왼쪽 서브트리
        inorder(mid + 1, end, depth + 1);   // 오른쪽 서브트리
    }

    public static void main(String[] args) throws IOException {
        //초기세팅
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        k = Integer.parseInt(br.readLine());
        nodeArr = new int[(int) Math.pow(2, k) - 1];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < nodeArr.length; i++) {
            nodeArr[i] = Integer.parseInt(st.nextToken());
        }

        // k개의 레벨 리스트 준비
        for (int i = 0; i < k; i++) {
            levelLists.add(new ArrayList<>());
        }
        //초기세팅 끝

        //레벨 찾기
        inorder(0, nodeArr.length - 1, 0);

        // 결과 출력
        for (int i = 0; i < k; i++) {
            for (int val : levelLists.get(i)) {
                System.out.print(val + " ");
            }
            System.out.println();
        }
    }
}

 

 

마무리하며:

처음 문제를 접했을 때는 이해하기 어렵지 않았고 난이도도 낮아 보여 쉽게 풀 수 있을 것이라 생각했다. 하지만 트리 문제의 본질을 간과하여 분할 기법을 떠올리지 못한 점이 아쉬움으로 남는다. 이러한 아이디어를 알고 나면 구현 자체는 어렵지 않지만, 그 아이디어를 스스로 발견하는 것 또한 중요한 능력이므로 앞으로는 이 부분을 더 키워야겠다고 생각했다.

 

 

감사합니다.