BOJ_트리 순회_1991 (Java, C++)

문제 링크

성능 요약

Java - 메모리: 14208 KB, 시간: 108 ms
C++ - 메모리: 2020 KB, 시간: 0 ms

분류

재귀, 트리

제출 일자

2024년 12월 18일 15:57:14

문제 설명

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

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

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

가 된다.

입력

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

출력

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

느낀점

• 비슷한 구조의 코드가 반복되더라도 복붙하지말고 직접 쓸것.
• 다른 함수나 변수가 잘못 쓰일 수 있음
• 노드가 문자 순서대로 입력되는 줄 알고 반복문의 i변수를 인덱스로 사용했던걸, idx 변수로 바꾸면서 일관되게 수정되지 않아 디버깅이 오래걸림.
• 순회 순서만 다른 각 재귀함수를 복붙해서 사용했더니 특정 메서드 안에서 다른 메서드를 부르는 불상사.. 복붙 금지. 머리 속 논리에 따라 직접 작성할 것.

설계 : 20분

• 배열을 안 두고 노드 클래스만 정의해서 root 노드부터 출력하도록 하려고 했지만, 그렇게 하면 불규칙하게 입력되는 노드를 트리 형태로 생성하기 어려움.
• 노드 클래스 정의를 안하고 이진트리의 규칙을 사용해 배열로 순회하려고 했지만, 완전 이진트리가 아니라서 오류가 날 수 있고, left, right 로 두개의 배열을 생성해야 함.
• 따라서 Node 클래스와 배열을 모두 사용하기로 함.
• 문자 - ‘A’ 를 배열의 인덱스로 가져 0부터 각 문자가 순서대로 노드를 이루도록 했다.
• 전위순회, 중위순회, 후위순회를 각각의 재귀함수로 정의했다.

구현(Java)

• 구현 시간: 60분

/**
 * Author: yngbao97, Yuk Yejin
 * Problem: 트리 순회_1991
 * Date: 2024.12.16
 */

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

public class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;
    static Node[] tree;

	public static void main(String[] args) throws Exception {

		br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int n = Integer.parseInt(br.readLine());
        tree = new Node[n];

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            char c = st.nextToken().charAt(0);
            int idx = c - 'A';
            tree[idx] = new Node(c);
            char left = st.nextToken().charAt(0);
            char right = st.nextToken().charAt(0);

            if (left != '.') tree[idx].left = left - 'A';
            else tree[idx].left = -1;

            if (right != '.') tree[idx].right = right - 'A';
            else tree[idx].right = -1;
        }

        preorder(tree[0]);
        bw.write("\n");
        inorder(tree[0]);
        bw.write("\n");
        postorder(tree[0]);
		
		bw.flush();
		bw.close();
		br.close();
	}

    public static void preorder (Node curr) throws IOException {

        bw.write(curr.c);
        if (curr.left != -1) preorder(tree[curr.left]);
        if (curr.right != -1) preorder(tree[curr.right]);
    }

    public static void inorder (Node curr) throws IOException {

        if (curr.left != -1) inorder(tree[curr.left]);
        bw.write(curr.c);
        if (curr.right != -1) inorder(tree[curr.right]);
    }

    public static void postorder (Node curr) throws IOException {

        if (curr.left != -1) postorder(tree[curr.left]);
        if (curr.right != -1) postorder(tree[curr.right]);
        bw.write(curr.c);
    }
}

class Node {
    char c;
    int left;
    int right;

    Node() {}
    Node (char c) {
        this.c = c;
    }
}

구현(C++)

• 구현 시간: 30분

/**
 * Author: yngbao97, Yuk Yejin
 * Problem: 트리 순회_1991
 * Date: 2024.12.18
 */

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

class Node {
    public :
        char c;
        int left;
        int right;

        Node() : c('-'), left(-1), right(-1) {}
        Node(char input) : c(input), left(-1), right(-1) {}
};

vector<Node> tree;

void preorder (Node& curr) {
    cout << curr.c;
    if (curr.left != -1) preorder(tree[curr.left]);
    if (curr.right != -1) preorder(tree[curr.right]);
}

void inorder (Node& curr) {
    if (curr.left != -1) inorder(tree[curr.left]);
    cout << curr.c;
    if (curr.right != -1) inorder(tree[curr.right]);
}

void postorder (Node& curr) {
    if (curr.left != -1) postorder(tree[curr.left]);
    if (curr.right != -1) postorder(tree[curr.right]);
    cout << curr.c;
}

int main() {

    int n;
    cin >> n;
    tree.resize(n);

    for (int i = 0; i < n; i++)
    {
        char c, left, right;
        cin >> c >> left >> right;

        int idx = c - 'A';
        tree[idx].c = c;
        if (left != '.') tree[idx].left = left - 'A';
        if (right != '.') tree[idx].right = right - 'A'; 
    }
    
    preorder(tree[0]);
    cout << "\n";
    inorder(tree[0]);
    cout << "\n";
    postorder(tree[0]);
    cout << "\n";

    return 0;
}

• 알게 된 점
  • 전역변수로 선언하고 싶을때는 main() 함수 이전에 외부에 선언한다.
  • vector는 사이즈를 정해주지 않으면 요소가 추가될때마다 resize되므로, 사이즈를 처음부터 정해주면 좋은데 main 함수 안에서만 그 크기를 알 수 있다면 resize() 메서드를 사용해서 재정의 할 수 있다.