문제

이해

트리의 순회 방식 (prefix, infix, postfix)에 따라 알맞게 이진트리를 출력하면 된다.

이 문제는 입력이 독특한데 입력은 노드의 개수만큼 줄이 입력된다.

각 줄은 노드의 이름, 그리고 2개 존재할 수 있는 좌우 자식 노드 정보가 담겨있다.

자식 노드가 없는 경우 "."을 입력받는다.

접근

문제는 총 2개의 과정으로 이루어진다.
1. 트리의 저장
2. 출력 (순회)

이진트리를 표현할 수 있는 방법은 다양하다. 해시 맵이나 배열처럼 노드에 고정된 인덱스를 배정하거나 연결리스트로 표현할 수도 있다.

배열을 사용하는 방법은 루트 노드 1을 기준으로 인덱스를 배정한다. 규칙은 다음과 같다.

노드 i의 왼쪽 자식 노드 = i 2
노드 i의 오른쪽 자식 노드 = i 2 + 1

배열을 통해 저장하는 방법은 이 문제에서 적절하지 않은 것 같다. 왜냐하면 배열에 저장하려면 입력 받을 때마다 저장할 공간의 인덱스를 갱신해야 하는데 문자로 입력받는 경우 최초에 트리 내에서 위치를 모른다.

예를 들어, 우리는 A 노드가 루트 노드, 즉 1번인 것은 알지만 최초 입력으로 E 노드가 입력되었다면 이 E 노드를 배열 상에서 어디에 배치해야 할까?

배치하기 위해서는 E 노드의 부모 노드 정보가 필요하기 때문에 뒤에서의 입력 정보를 알아야 한다. 따라서, 부적절해 보인다.

연결리스트로 표현하는 방법은 자바로는 클래스를 정의하면 된다.

node 클래스의 멤버 변수로 현재 노드, 좌우 자식 노드를 선언하고 입력받을 때마다 이를 저장한다.

연결리스트 표현은 어느 노드가 먼저 입력되더라도 안정적으로 정보를 저장할 수 있다.

다음으로는 출력 방법을 보자. prefix, infix, postfix는 각각 규칙이 존재한다. 이는 재귀를 통한 트리의 순회로 구현할 수 있다.

단, 재귀를 통한 순회에서는 자식 노드를 탐색하고 부모 노드로 돌아가야 하기 때문에 순회 규칙에 따라 출력할지의 여부는 boolean형 변수를 통해 판단한다.

예를 들어, infix의 경우 왼쪽 자식 노드가 최우선이기 때문에 현재 부모 노드를 출력하기 전에 왼쪽 자식 노드의 부분 트리를 모두 탐색해야만 한다.

코드

package java_baekjoon;

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

public class prob1991 {
    static StringBuilder sb;
    static ArrayList<node> tree = new ArrayList<>();
    static int N;

    static class node {
        String now;
        String l_child;
        String r_child;
        boolean visited;

        public node(String now, String l_child, String r_child) {
            this.now = now;
            this.l_child = l_child;
            this.r_child = r_child;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Queue<Integer> q = new LinkedList<>();

        N = Integer.parseInt(br.readLine());
        int root = 1;

        for (int i = 0; i < N; i++) {
            String[] input = br.readLine().split(" ");

            if (input[0].equals("A")) {
                root = i;
            }

            tree.add(new node(input[0], input[1], input[2]));
        }

        sb = new StringBuilder();
        prefix(root);
        for (int i = 0; i < tree.size(); i++) {
            tree.get(i).visited = false;
        }
        System.out.println(sb.toString());

        sb = new StringBuilder();
        infix(root);
        for (int i = 0; i < tree.size(); i++) {
            tree.get(i).visited = false;
        }
        System.out.println(sb.toString());

        sb = new StringBuilder();
        postfix(root);
        for (int i = 0; i < tree.size(); i++) {
        tree.get(i).visited = false;
        }
        System.out.println(sb.toString());
    }

    static void prefix(int node_pos) {
        node cur_node = tree.get(node_pos);

        if (cur_node.visited) {
            return;
        }
        cur_node.visited = true;
        sb.append(cur_node.now);

        for (int i = 0; i < tree.size(); i++) {
            if (tree.get(i).now.equals(cur_node.l_child)) {
                prefix(i);
            }
        }

        for (int i = 0; i < tree.size(); i++) {
            if (tree.get(i).now.equals(cur_node.r_child)) {
                prefix(i);
            }
        }
    }

    static void infix(int node_pos) {
        node cur_node = tree.get(node_pos);

        if (cur_node.visited) {
            return;
        }

        for (int i = 0; i < tree.size(); i++) {
            if (tree.get(i).now.equals(cur_node.l_child)) {
                infix(i);
            }
        }

        cur_node.visited = true;
        sb.append(cur_node.now);

        for (int i = 0; i < tree.size(); i++) {
            if (tree.get(i).now.equals(cur_node.r_child)) {
                infix(i);
            }
        }
    }

    static void postfix(int node_pos) {
        node cur_node = tree.get(node_pos);

        if (cur_node.visited) {
            return;
        }

        for (int i = 0; i < tree.size(); i++) {
            if (tree.get(i).now.equals(cur_node.l_child)) {
                postfix(i);
            }
        }

        for (int i = 0; i < tree.size(); i++) {
            if (tree.get(i).now.equals(cur_node.r_child)) {
                postfix(i);
            }
        }

        cur_node.visited = true;
        sb.append(cur_node.now);
    }
}

저장은 위에서와 같이 node 클래스를 정의하여 ArrayList에 저장했다. A 노드는 루트 노드이기 때문에 중요한 정보이다. 왜냐하면 순회의 시작 지점이기 때문이다. 따라서, 입력받을 때 따로 기록한다.

순회는 모두 같은 구성으로 되어있다. StringBuilder를 초기화하고 루트부터 순회에 들어간다. 순회가 끝나면 모든 노드의 visited를 false로 초기화하고 출력한다.

순회의 내부를 보자. 이전에 출력된 노드라면 빠져나오고 아니라면 자식노드를 탐색한다. ArrayList를 탐색하여 현재 노드의 자식 노드와 같은 노드의 인덱스를 찾는다. 해당 인덱스가 다음으로 순회될 노드이기 때문에 재귀의 파라미터로 들어간다.

출력은 순회 규칙에 따라 위치를 다르게 한다.

추가

코드를 작성하고 보니 ArrayList형에서 다음 순회 위치를 찾는 반복문이 조금 비효율적으로 보인다. 더 좋은 방법이 있을 것 같다.

        for (int i = 0; i < tree.size(); i++) {
            if (tree.get(i).now.equals(cur_node.r_child)) {
                postfix(i);
            }
        }

결과