[백준] 1991번 - 트리 순회 풀이 및 코드 분석 (Java)

문제 링크

성능 요약

메모리: 273920 KB, 시간: 296 ms

이번 문제는 이진 트리의 전위, 중위, 후위 순회를 구현하는 문제입니다.
트리는 배열을 활용한 완전 이진 트리 방식으로 저장하고,
이를 바탕으로 재귀를 이용한 트리 순회를 구현합니다.

---

1. 문제 분석

트리를 순회하는 방식은 다음과 같습니다.

순회 방식	순서
전위 순회	(루트) → (왼쪽 자식) → (오른쪽 자식)
중위 순회	(왼쪽 자식) → (루트) → (오른쪽 자식)
후위 순회	(왼쪽 자식) → (오른쪽 자식) → (루트)

 

입력으로 루트(A)부터 시작하는 트리 구조가 주어지며, 이를 기반으로 세 가지 순회 결과를 출력해야 합니다.

예제 입력

7
A B C
B D .
C E F
E . .
F . G
D . .
G . .

예제 출력

ABDCEFG
DBAECFG
DBEGFCA

---

2. 해결 방법

트리를 저장하는 방식

• 트리를 배열을 이용한 완전 이진 트리 형태로 저장합니다.
• 배열의 인덱스를 이용해 부모-자식 관계를 저장하는 방식입니다.
• 트리에서 i번째 노드에 대해:
  • 왼쪽 자식은 2 * i
  • 오른쪽 자식은 2 * i + 1 로 표현할 수 있습니다.

트리 순회 구현

• 전위, 중위, 후위 순회를 재귀로 구현합니다.
• 각 순회 함수는 재귀적으로 왼쪽과 오른쪽 자식을 탐색합니다.

---

3. 코드 구현

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {

  static String[] arr;
  static StringBuilder fsb = new StringBuilder();
  static StringBuilder msb = new StringBuilder();
  static StringBuilder bsb = new StringBuilder();

  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int N = Integer.parseInt(br.readLine());
    arr = new String[(int) (Math.pow(2, N))]; // 트리 저장 배열 (완전 이진 트리 형태)
    arr[1] = "A"; // 루트는 항상 A

    for (int i = 0; i < N; i++) {
      String[] tmp = br.readLine().split(" ");
      int idx = Arrays.asList(arr).indexOf(tmp[0]); // 부모 노드의 인덱스 찾기

      if (!tmp[1].equals("."))
        arr[2 * idx] = tmp[1]; // 왼쪽 자식 저장

      if (!tmp[2].equals("."))
        arr[2 * idx + 1] = tmp[2]; // 오른쪽 자식 저장
    }

    // 트리 순회 실행
    front(1);  // 전위 순회
    middle(1); // 중위 순회
    back(1);   // 후위 순회

    // 결과 출력
    System.out.println(fsb);
    System.out.println(msb);
    System.out.println(bsb);
  }

  // 후위 순회 (Postorder): 왼쪽 -> 오른쪽 -> 루트
  private static void back(int i) {
    if (i >= arr.length || arr[i] == null) return;
    back(2 * i);
    back(2 * i + 1);
    bsb.append(arr[i]);
  }

  // 중위 순회 (Inorder): 왼쪽 -> 루트 -> 오른쪽
  private static void middle(int i) {
    if (i >= arr.length || arr[i] == null) return;
    middle(2 * i);
    msb.append(arr[i]);
    middle(2 * i + 1);
  }

  // 전위 순회 (Preorder): 루트 -> 왼쪽 -> 오른쪽
  private static void front(int i) {
    if (i >= arr.length || arr[i] == null) return;
    fsb.append(arr[i]);
    front(2 * i);
    front(2 * i + 1);
  }
}

---

4. 코드 분석

트리 저장 방식

• 트리를 완전 이진 트리 배열 구조로 저장했습니다.
• arr[1] = "A"; → 루트 노드는 항상 "A" 입니다.
• 노드의 위치를 배열 인덱스로 표현하고, 2 * idx, 2 * idx + 1을 활용해 부모-자식 관계를 유지합니다.

트리 순회 구현

• 재귀 함수를 사용하여 전위, 중위, 후위 순회를 구현했습니다.
• front(i), middle(i), back(i) 각각의 함수가 해당 순회 방식에 맞춰 트리를 탐색합니다.

시간 복잡도 분석

• 트리의 노드 개수 N ≤ 26 이므로, 각 순회 함수의 시간 복잡도는 O(N) 입니다.
• 배열을 이용해 노드를 빠르게 찾을 수 있어 탐색 속도는 O(1) 입니다.

---

5. 개선할 점 및 대체 방법

❌ 배열을 이용한 방식의 한계점

• Arrays.asList(arr).indexOf(tmp[0]) → 배열에서 인덱스를 찾는 과정이 O(N)으로 비효율적입니다.
• 트리가 완전 이진 트리가 아닐 경우 배열 낭비가 발생할 수 있습니다.

✅ 대체 방법 (Map을 활용한 트리 저장)

• HashMap을 사용하면 트리 노드를 효율적으로 저장할 수 있습니다.
• Map<Character, Node> 형태로 저장하면 O(1) 조회 가능하며, 메모리 낭비를 줄일 수 있습니다.