[백준 1991] 트리 순회 (java)

링크

나의 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        String s = "";
        s = bf.readLine();

        // 노드 개수 입력
        int NodeTotal = Integer.parseInt(s);

        // 입력받은 갯수에 맞는 노드 생성
        Node[] nodes = new Node[NodeTotal];

        // 생성한 노드에 대해 미리 값 입력
        for (int i = 0; i < NodeTotal; i++) {
            nodes[i] = new Node(i);
        }

        // 노드 개수만큼 입력받음
        for (int i = 0; i < NodeTotal; i++) {
            s = bf.readLine();
            String[] strs = s.split(" ");

            // left, right를 연결할 노드
            int n = (int)(strs[0].toCharArray()[0] - 'A');

            if (!strs[1].equals(".")) {
                // . 이 아닐 경우에만 입력
                int leftValue = (int)(strs[1].toCharArray()[0] - 'A');
                nodes[n].setLeft(nodes[leftValue]);
            }
            if (!strs[2].equals(".")) {
                // . 이 아닐 경우에만 입력
                int rightValue = (int)(strs[2].toCharArray()[0] - 'A');
                nodes[n].setRight(nodes[rightValue]);
            }
        }

        nodes[0].preorderTraversal();   // 전위 순회 출력
        System.out.println();
        nodes[0].inorderTraversal();   // 중위 순회 출력
        System.out.println();
        nodes[0].postorderTraversal();   // 후위 순회 출력
        System.out.println();
    }
}

class Node {
    private int value;
    private Node left;
    private Node right;

    Node() {
        // 미사용
    }

    Node(int value) {
        this(value, null, null);
    }

    Node(int value, Node left, Node right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public void setRight(Node right) {
        this.right = right;
    }

    public void printValue() {
        // int 값을 글자에 맞게 출력
        System.out.print((char)('A' + value));
    }

    public void preorderTraversal() {
        // 전위 순회
        // 루트 왼쪽 오른쪽

        printValue();

        if (left != null) {
            left.preorderTraversal();
        }
        if (right != null) {
            right.preorderTraversal();
        }
    }

    public void inorderTraversal() {
        // 중위 순회
        // 왼쪽 루트 오른쪽
        if (left != null) {
            left.inorderTraversal();
        }
        printValue();
        if (right != null) {
            right.inorderTraversal();
        }
    }

    public void postorderTraversal() {
        // 후위 순회
        // 왼쪽 오른쪽 루트
        if (left != null) {
            left.postorderTraversal();
        }
        if (right != null) {
            right.postorderTraversal();
        }
        printValue();
    }
}

이번 문제의 경우에는 노드의 갯수와 해당 값을 미리 지정할 수 있었다. 때문에, Tree 구조를 엮어나가는 방식이 아닌 미리 노드배열을 만들고 각각 길을 연결해주는 방식으로 처리했다. 이렇게 처리했기 때문에, 트리 구조처럼 작동하는 것은 순회할 때 말곤 없는 것 같다.

트리를 만들어가면서 처리할 수도 있었지만, 그럴 때 마다 노드가 존재하는지 확인하는 과정이 이 문제에서는 불필요하다고 생각했기 때문이다. 128ms 결과로 속도도 괜찮았지만, 노드 존재 여부를 확인하며 처리해도 124ms를 달성할 수 있어 불필요한 고민이었나 싶다.

모범 답안

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Node{
    char data;
    Node left,right;
    public Node(char data) {this.data=data;}
}
class Tree{
    Node root;//처음엔 null상태
    void add(char data,char leftNode,char rightNode) {
        if(root==null) {//root노드가 비어있는상태, 처음상태
            if(data!='.') {
                root=new Node(data);
            }
            if(leftNode!='.') {
                root.left=new Node(leftNode);
            }
            if(rightNode!='.') {
                root.right=new Node(rightNode);
            }
        }else {
            search(root, data, leftNode, rightNode);
        }
    }

    void search(Node root,char data,char leftNode,char rightNode) {
        if(root==null) {
            return;
        }
        else if(root.data==data) {
            if(leftNode!='.') {
                root.left=new Node(leftNode);
            }
            if(rightNode!='.') {
                root.right=new Node(rightNode);
            }
        }
        else {
            search(root.left, data, leftNode, rightNode);
            search(root.right, data, leftNode, rightNode);
        }

    }

    //전위순회, left-root-right
    void preorder(Node root) {
        System.out.print(root.data);
        if(root.left!=null)preorder(root.left);
        if(root.right!=null)preorder(root.right);
    }

    //중위순회 , root-left-right-
    void inorder(Node root) {
        if(root.left!=null)inorder(root.left);
        System.out.print(root.data);
        if(root.right!=null)inorder(root.right);
    }

    //후위순회 , left-right-root
    void postorder(Node root) {
        if(root.left!=null)postorder(root.left);
        if(root.right!=null)postorder(root.right);
        System.out.print(root.data);
    }

}

public class Main {

    public static void main(String[] args) throws NumberFormatException, IOException {
        // TODO Auto-generated method stub
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int num=Integer.parseInt(br.readLine());

        Tree tree=new Tree();
        char data[];

        for(int i=0;i<num;i++) {
            data=br.readLine().replace(" ", "").toCharArray();
            tree.add(data[0], data[1], data[2]);
        }

        tree.preorder(tree.root);
        System.out.println();
        tree.inorder(tree.root);
        System.out.println();
        tree.postorder(tree.root);
        br.close();
    }

}

다른 이들 대부분의 코드는 트리 클래스를 만들고, 그 안에 root 노트를 만들어 처리했다. 노드에 메소드를 넣는 나의 코드보다, 이 것이 정형화된 형식이라 생각한다.

그리고 입력받은 데이터를 처리하는 과정을 더욱 간결하게 처리했다. 모두 char로 처리하여 가독성이 높다. 속도도 124ms로 더 좋다. 이렇게 처리하도록 노력해야겠다.