[SWEA][DFS][Java] 1231. 중위순회 : D4

문제 링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=4&contestProbId=AV140YnqAIECFAYD&categoryId=AV140YnqAIECFAYD&categoryType=CODE&problemTitle=&orderBy=INQUERY_COUNT&selectCodeLang=ALL&select-1=4&pageSize=10&pageIndex=2

 

 

이 문제는 이진 트리가 주어졌을 때, 각 노드에 저장된 문자를 특정 순서로 출력하는 문제이다.

핵심은 트리를 어떻게 탐색하느냐인데, 이 문제에서 요구하는 방식은 중위 순회 (Inorder Traversal)이다. 

---

중위 순회(inorder traversal)란?

이진 트리를 순회하는 방법 중 하나로, 순서는 다음과 같다.

왼쪽 자식 → 현재 노드 → 오른쪽 자식

 

 

      A
     | | 
    B   C

중위 순회 결과:

B -> A -> C

---

전체 흐름

1. 각 노드에 대해:
   1. 문자 정보 저장
   2. 왼쪽 / 오른쪽 자식 연결
2. 루트(1번 노드)부터 시작
3. 다음 순서로 탐색:
   1. 왼쪽 자식 방문
   2. 현재 노드 출력
   3. 오른쪽 자식 방문

자료구조 설계

1. 트리 구조 저장

static List<Integer>[] arr;

• 각 인덱스 = 노드 번호
• 리스트 = 자식 노드 (왼쪽, 오른쪽)

---

2. 노드 값 저장

static char[] chars;

• 각 노드가 가지는 문자 저장

---

3. 결과 저장

static StringBuilder result;

• 순회 결과를 문자열로 누적

---

핵심 로직 (DFS)

public static void dfs(int i){
    // 왼쪽 자식
    if(arr[i].size() >= 1){ 
        dfs(arr[i].get(0));
    }

    // 현재 노드
    result.append(chars[i]);

    // 오른쪽 자식
    if(arr[i].size() == 2){
        dfs(arr[i].get(1));
    }
}

---

시간복잡도

• 모든 노드를 한 번씩 방문하므로, O(N)

---

전체 코드

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

class Solution {
    static List<Integer>[] arr;
    static char[] chars;
    static StringBuilder result;

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

        for(int test_case = 1; test_case <= 10; test_case++) {
            sb.append("#").append(test_case).append(" ");

            int N = Integer.parseInt(br.readLine());
            arr = new ArrayList[N+1];
            chars = new char[N+1];

            for(int i = 1; i <= N; i++){
                arr[i] = new ArrayList<>();
            }

            for(int i = 0; i < N; i++){
                st = new StringTokenizer(br.readLine());
                int num = Integer.parseInt(st.nextToken());
                char ch = st.nextToken().charAt(0);
                chars[num] = ch;

                if(st.hasMoreTokens()){
                    arr[num].add(Integer.parseInt(st.nextToken()));
                }
                if(st.hasMoreTokens()){
                    arr[num].add(Integer.parseInt(st.nextToken()));
                }
            }

            result = new StringBuilder();
            dfs(1);

            sb.append(result).append("\n");
        }

        System.out.print(sb);
    }

    public static void dfs(int i){
        if(arr[i].size() >= 1){
            dfs(arr[i].get(0));
        }

        result.append(chars[i]);

        if(arr[i].size() == 2){
            dfs(arr[i].get(1));
        }
    }
}