[백준][1991] 트리 순회

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	14784	9033	6904	62.741%

문제

이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오.

예를 들어 위와 같은 이진 트리가 입력되면,

전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)
중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)
후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)
가 된다.

입력

첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자 대문자로 매겨지며, 항상 A가 루트 노드가 된다. 자식 노드가 없는 경우에는 .으로 표현된다.

출력

첫째 줄에 전위 순회, 둘째 줄에 중위 순회, 셋째 줄에 후위 순회한 결과를 출력한다. 각 줄에 N개의 알파벳을 공백 없이 출력하면 된다.

예제 입력

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

예제 출력

ABDCEFG
DBAECFG
DBEGFCA

코드

package bj;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class bj1991 {

    public static int N;
    public static List<Integer> adjList[];
    public static String pre, in, post;

    public static void main(String[] args) throws NumberFormatException, IOException {
        // TODO Auto-generated method stub

        System.setIn(new FileInputStream("C://sample_input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        for(int tc=1; tc<=1; tc++) {

            N = Integer.parseInt(br.readLine());
            adjList = new ArrayList[65+26];
            for(int i=65; i<adjList.length; i++) {
                adjList[i] = new ArrayList<Integer>();
            }

            for(int i=1; i<=N; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                // TODO String -> char로 변환하는 더 좋은 방법은?
                int m = st.nextToken().charAt(0);
                int l = st.nextToken().charAt(0);
                int r = st.nextToken().charAt(0);

                adjList[m].add(l);
                adjList[m].add(r);

            }

            pre = "";
            in = "";
            post = "";
            search('A');

            bw.flush();
            bw.write(pre + "\n");
            bw.write(in + "\n");
            bw.write(post + "\n");

        }

        bw.close();

    }

    public static void search(int curr) {

        char currChar = (char) curr;
        pre += currChar;

        boolean isRoot = false;
        for(int i=0; i<adjList[curr].size(); i++) {
            int next = adjList[curr].get(i);
            if(next == '.') {
                if(i==0) {
                    in += currChar;
                    isRoot = true;
                }
                continue;
            }
            search(next);
            if(i==0) {
                in += currChar;
                isRoot = true;
            }
        }

        if(!isRoot) {
            in += currChar;
        }
        post += currChar;

    }

}

모범답안

package bj;

import java.io.*;
import java.util.*;
public class bj1991_solution {

    static class NODE // 노드 클래스
    {
        String val;
        int parent, right, left;
        public NODE(String val) {
            this.val = val;
            this.parent = this.right = this.left = -1;
        }
    };
    static int N;
    static NODE A[] = new NODE[26];
    static String tmpstr;
    static void preOrder(int node)
    {   
        System.out.print(A[node].val);
        if(A[node].left > -1) preOrder(A[node].left);
        if(A[node].right > -1) preOrder(A[node].right);
    }
    static void inOrder(int node)
    {   
        if(A[node].left > -1) inOrder(A[node].left);
        System.out.print(A[node].val);
        if(A[node].right > -1) inOrder(A[node].right);
    }
    static void postOrder(int node)
    {   
        if(A[node].left > -1) postOrder(A[node].left);
        if(A[node].right > -1) postOrder(A[node].right);
        System.out.print(A[node].val);
    }
    public static void main(String[] args) throws Exception
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        for(int i=0;i<26;i++)
        {
            A[i] = new NODE(Character.toString((char)(i+'A')));
        }

        for(int i=0;i<N;i++)
        {
            char n, l, r;
            tmpstr = br.readLine();
            n=tmpstr.charAt(0);
            l=tmpstr.charAt(2);
            r=tmpstr.charAt(4);
            if(l!='.')
            {
                A[n-'A'].left = l-'A';
                A[l-'A'].parent = n-'A';
            }
            if(r!='.')
            {
                A[n-'A'].right = r-'A';
                A[r-'A'].parent = n-'A';
            }
        }
        preOrder(0);System.out.println();
        inOrder(0);System.out.println();
        postOrder(0);System.out.println();
    }

}

풀이

DFS로 순회하면서 다소 주먹구구식으로 무식하게 풀었다.
솔직히 내가 푼방식은 뭐라 설명하기도 애매한 소스라 더이상 언급할 가치는 없는 것 같다.

모범답안이 중요한데, 학부때 알고리즘(자료구조) 책에 나온 예제랑 똑같다. 단순하고 직관적이다.
코드를 보면 크게 설명할 필요는 없을 것 같다.