9934번: 완전 이진 트리

문제

상근이는 깊이가 K인 완전 이진 트리 모양의 도로를 가진 도시를 방문합니다. 빌딩을 방문하는 순서는 트리에서의 중위 순회(In-order Traversal) 방식과 동일합니다. (왼쪽 자식 방문 -> 현재 노드 방문 -> 오른쪽 자식 방문) 상근이가 방문한 빌딩의 번호 순서가 주어졌을 때, 각 레벨(깊이)에 있는 빌딩의 번호를 위에서부터 아래로 구하는 문제입니다.

• 입력: 첫째 줄에 깊이 K (1 ≤ K ≤ 10)가 주어지고, 둘째 줄에 상근이가 방문한 빌딩의 번호 2^K - 1개가 주어집니다.
• 출력: 첫째 줄부터 K개의 줄에 걸쳐 각 레벨에 있는 빌딩의 번호를 공백으로 구분하여 출력합니다.

링크: https://www.acmicpc.net/problem/9934

풀이: 중위 순회의 성질과 분할 정복

완전 이진 트리를 중위 순회한 결과에서 찾을 수 있는 가장 핵심적인 특징은 "해당 서브트리의 루트 노드는 항상 탐색 구간의 정중앙에 위치한다"는 점입니다. 이 성질을 이용하여 분할 정복 방식의 재귀 탐색으로 전체 트리를 복원할 수 있습니다.

1. 정답 리스트 배열 초기화: 트리의 각 깊이(레벨)별로 노드를 순서대로 저장하기 위해, 크기가 K인 ArrayList 배열 ans를 선언하고 초기화합니다.
2. 루트 노드 탐색 (중앙값 찾기): 주어진 수열에서 현재 구간의 시작 인덱스가 start이고 끝 인덱스가 end일 때, 정중앙의 인덱스는 mid = (start + end) / 2가 됩니다. 이 위치의 노드가 현재 구간(서브트리)의 루트 노드이므로, 해당 깊이 h의 정답 리스트 ans[h]에 값을 추가합니다.
3. 분할 정복 (재귀 호출): 루트 노드(mid)를 찾아냈다면, 이를 기준으로 왼쪽 절반은 왼쪽 자식 서브트리, 오른쪽 절반은 오른쪽 자식 서브트리로 나눌 수 있습니다.
   • 왼쪽 서브트리: 탐색 깊이를 h + 1로 늘리고, 구간을 start부터 mid - 1까지로 좁혀서 재귀 호출(go(h + 1, start, mid - 1))합니다.
   • 오른쪽 서브트리: 탐색 깊이를 h + 1로 늘리고, 구간을 mid + 1부터 end까지로 좁혀서 재귀 호출(go(h + 1, mid + 1, end))합니다.
4. 기저 조건 (종료 조건): 현재 탐색 구간의 시작점 start가 끝점 end보다 커지면 유효하지 않은 구간이므로 즉시 탐색을 종료(return)합니다. (또는 start == end일 때 더 이상 나눌 수 없는 리프 노드이므로, 리스트에 추가 후 바로 종료하여 재귀 호출의 깊이를 최적화할 수 있습니다.)

코드

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

public class Main {
    static List<Integer>[] ans;
    static int[] a;

    public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

       int k = Integer.parseInt(br.readLine());
       int n = 1;

       // 깊이 K만큼의 정답 저장용 리스트 배열 초기화 및 총 노드 수(2^k - 1) 계산
       ans = new ArrayList[k];
       for (int i = 0; i < k; i++) {
          ans[i] = new ArrayList<>();
          n *= 2;
       }
       n -= 1;

       // 중위 순회 결과 입력
       a = new int[n];
       StringTokenizer st = new StringTokenizer(br.readLine());
       for (int i = 0; i < n; i++) {
          a[i] = Integer.parseInt(st.nextToken());
       }
       
       // 재귀 탐색 시작 (초기 깊이 0, 시작 인덱스 0, 끝 인덱스 n - 1)
       go(0, 0, n - 1);

       // 깊이별로 저장된 빌딩 번호 출력
       for (int i = 0; i < k; i++) {
          for (int j : ans[i])
             bw.write(j + " ");
          bw.write("\n");
       }

       bw.flush();
       bw.close();
       br.close();
    }

    // 분할 정복을 수행하는 재귀 메서드
    // h: 현재 깊이, start: 탐색 시작 인덱스, end: 탐색 끝 인덱스
    static void go(int h, int start, int end) {
       // 기저 조건 1: 유효하지 않은 탐색 구간일 경우 안전하게 종료
       if (start > end) return;
       
       // 현재 서브트리의 루트 노드(구간의 정중앙) 인덱스 계산
       int mid = (start + end) / 2;
       
       // 해당 깊이의 리스트에 루트 노드 추가
       ans[h].add(a[mid]);
       
       // 기저 조건 2: 구간 크기가 1이면(리프 노드) 불필요한 재귀 호출 없이 종료
       if (start == end)
          return;
          
       // 왼쪽 서브트리 탐색
       go(h + 1, start, mid - 1);
       // 오른쪽 서브트리 탐색
       go(h + 1, mid + 1, end);
    }
}

알고리즘 분류

트리 (Tree), 재귀 (Recursion), 분할 정복 (Divide and Conquer)