[백준, 1991번] 트리 순회 (트리, 재귀, Java)

문제설명

입력 & 출력

나의 풀이

문제 접근 방법

"백준 - 트리 순회" 문제는 순회 방식인 전위, 중위, 후위 순회 방식을 사용하여 트리를 탐색하는 문제입니다. 문제의 핵심은 트리 구조를 직접 구현하는 것입니다.

 

이 문제에서 시작 노드는 항상 'A'로 주어지며, 입력에서 '.'은 해당 자식 노드가 없음을 의미합니다. 이를 고려하여 트리를 구성하는 것이 첫 번째 목표입니다. Map 자료구조를 사용하면 키를 부모 노드로, 값을 Node 객체로 설정하면 부모-자식 관계를 손쉽게 연결할 수 있습니다.

[JAVA] HashMap 이란 ❓ (1/2)

---

예제 입력 1번을 예로 들어 설명하자면 첫번째 노드 A B C가 입력이 될 때 각 노드를 먼저 생성합니다.

 

그리고 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드를 연결해줍니다.

---

 

2번째 입력에서는 B의 오른쪽 자식 노드가 '.'로 노드가 없으니깐 위와 같이 트리가 형성됩니다.

---

 

문제 접근 방법

 

코드가 길긴한데 각 역할 별로 구분하여 살펴보겠습니다.

 

1. Node 클래스

 

Node 클래스에서는 해당 노드의 실제 값을 저장하는 value와 왼쪽 자식 노드를 가리키는 left, 오른쪽 자식 노드를 가리키는 right라는 참조 변수가 존재합니다.

 

즉, 이 클래스는 이진 트리의 각 노드를 표현하며, 노드 간의 부모-자식 관계를 연결하는 역할을 합니다.

---

2.Main 클래스

public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer token;
        Map<Character,Node> tree = new HashMap<>(); // 노드 저장용
        
        int N = Integer.parseInt(br.readLine());

        for (int i = 0; i < N; i++) {
            token = new StringTokenizer(br.readLine());

            char parents = token.nextToken().charAt(0); // 부모 노드
            char left = token.nextToken().charAt(0); // 왼쪽 자식 노드
            char right = token.nextToken().charAt(0); // 오른쪽 자식 노드

            // 루트 노드 생성
            tree.putIfAbsent(parents, new Node(parents));

            // 왼쪽 자식 노드가 있다면 생성 후 연결
            if(left != '.'){
                tree.putIfAbsent(left,new Node(left));
                tree.get(parents).left = tree.get(left);
            }

            // 오른쪽 자식 노드가 있다면 생성 후 연결
            if(right != '.'){
                tree.putIfAbsent(right,new Node(right));
                tree.get(parents).right = tree.get(right);
            }
        }

        Node A = tree.get('A'); // 노드의 시작은 항상 A
        preOrder(A);
        System.out.println();
        inOrder(A);
        System.out.println();
        postOrder(A);
    }

 

main 클래스에서는 먼저 입력받은 문자열을 공백을 기준으로 토큰화하여 부모 노드와 두 자식 노드(왼쪽, 오른쪽)를 구분합니다.

 

그 다음 HashMap을 사용해 각 노드를 생성하고 저장하는데, putIfAbsent 메서드를 통해 중복을 방지하면서 부모-자식 관계를 설정합니다.

 

반복문이 끝나게 되면 입력을 바탕으로 한 트리가 형성됩니다. 이 트리를 기준으로 전위, 중위, 후위 순회를 출력하여 마무리 해주면됩니다.

---

 

3. preOrder() ➡️ 전위 순회 함수

 

전위 순회(preorder)는 루트 노드를 먼저 방문한 후, 왼쪽 서브트리, 오른쪽 서브트리 순으로 방문하는 순회 방식입니다.

위 그림에서 볼 수 있듯이, 파란색(1)으로 표시된 루트 노드 A를 먼저 방문하고, 빨간색(2,3,5)으로 표시된 왼쪽 자식들을 순서대로 방문한 다음, 초록색(4,6,7)으로 표시된 오른쪽 자식들을 방문합니다.

 

이는 재귀적으로 각 서브트리에 대해서도 동일하게 적용되어, 모든 노드가 루트->왼쪽->오른쪽 순서로 방문됩니다.

public static void preOrder(Node node){
        if(node == null) return;
        System.out.print(node.value);
        preOrder(node.left);
        preOrder(node.right);
    }

 

코드를 살펴보면, 먼저 노드가 null인지 확인하여 순회할 수 없는 경우 바로 return합니다.

 

그런 다음 전위 순회의 특성에 따라 현재 노드를 먼저 출력하고, 재귀적으로 왼쪽 서브트리를 순회합니다.

 

왼쪽 서브트리의 순회가 끝나면 마찬가지로 재귀적으로 오른쪽 서브트리를 순회합니다. 이렇게 각 노드에서 루트->왼쪽->오른쪽 순서로 방문하면서 전체 트리를 전위 순회할 수 있습니다.

 

이러한 같은 방식으로 재귀 호출을 통해 전위, 중위, 후위 순회를 할 수 있습니다.