백준 1991번( 자바 )

Flash·2022년 2월 2일
0

BOJ-Algorithm

목록 보기
38/51
post-thumbnail

BST 구현

백준 1991번을 Java를 이용하여 풀어보았다. 트리를 다뤄보는 건 학교 자료구조 수업 시간에 대충 성적 받기용으로만 어설프게 한 후로 처음이었다. 뭐 아예 몰랐다고 해도 되겠다. 프로그래머스 카카오 블라인드 문제를 풀다가 트리 문제가 나왔는데 트리에 대한 지식이 전무해서 백준 트리 문제부터 풀어봐야겠다 싶어서 풀었다.

문제 링크 첨부한다.
https://www.acmicpc.net/problem/1991


이진 탐색 트리 구현

크게 새로운 노드를 추가해주는 add()search()를 구현하고 문제 조건대로 전위순회, 중위순회 그리고 후위순회로 출력하는 메소드를 구현했다.

먼저 add()search()를 아래 코드로 함께 살펴보자.

class Tree {
        Node root; // 모든 트리에는 root 노드가 있다. 클래스 변수로 선언하자

        void add(char data, char leftData, char rightData) {
            if (root == null) { // 루트가 아직 비어있으면
                root = new Node(data);
                if (leftData != '.') root.left = new Node(leftData);
                if (rightData != '.') root.right = new Node(rightData);
            } else search(root, data, leftData, rightData); // 들어갈 자리를 찾아주자
        }

        void search(Node curNode, char data, char leftData, char rightData) {
            if (curNode == null) return; // 끝까지 왔는데 자리 없으면 종료
            else if(curNode.data == data){ // 자리 찾음!!
                if (leftData != '.') curNode.left = new Node(leftData);
                if (rightData != '.') curNode.right = new Node(rightData);
            }
            else{
                search(curNode.left, data, leftData, rightData);
                search(curNode.right, data, leftData, rightData);
            }
        }

        ...
    }

add()

root 노드가 비어있을 때와 이미 있을 때를 구분해서 수행하자. 비어있으면 root 노드를 채워주고, 차 있으면 들어갈 자리를 찾아줄 search()를 수행하자.

왼쪽 재귀 검색과 오른쪽 재귀 검색을 통해서 새롭게 추가해주는 노드가 어디 위치해야 할지를 찾아주자.

위의 두 재귀를 수행해서 마지막 curNode.left 또는 curNode.right까지 찾아갔는데 만약 더이상 갈 곳이 없어 비어있는 ==null이라면 자리가 없는 놈이기 때문에 종료를 해주면 된다.

자리를 찾았으면 왼쪽과 오른쪽 노드를 연결해주면 된다.


순회 방식에 따른 출력 메소드

문제에서 요구한 것은 preorder, inorder 그리고 postorder 순서로 출력하는 것이었다.
아래 코드를 통해 살펴보자.


class Tree {
        Node root;

        ...

        void preorder(Node curNode) throws IOException { // root -> left -> right
            bfw.write(curNode.data+"");
            if(curNode.left!=null)  preorder(curNode.left);
            if(curNode.right!=null) preorder(curNode.right);
        }

        void inorder(Node curNode) throws IOException { // left -> root -> right
            if(curNode.left!=null)  inorder(curNode.left);
            bfw.write(curNode.data+"");
            if(curNode.right!=null) inorder(curNode.right);
        }

        void postorder(Node curNode) throws IOException { // left -> right -> root
            if(curNode.left!=null)  postorder(curNode.left);
            if(curNode.right!=null) postorder(curNode.right);
            bfw.write(curNode.data+"");
        }
    }

root 노드를 어느 타이밍에 출력해줄지만 한 칸씩 옮기면 되는 것이다.


BST를 처음 구현해보고 순회 방식에 따라 출력 메소드도 만들어 보았다. 또다른 트리 문제를 만나면 그때는 혼자의 힘으로 해결해보자. 아래는 내가 제출한 코드다.

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

public class boj1991 {
    static BufferedWriter bfw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String args[]) throws IOException {
        BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(bfr.readLine());
        Tree tree = new Tree();

        int n = Integer.parseInt(stk.nextToken());
        for (int i = 0; i < n; i++) {
            stk = new StringTokenizer(bfr.readLine());
            tree.add(stk.nextToken().charAt(0), stk.nextToken().charAt(0), stk.nextToken().charAt(0));
        }
        tree.preorder(tree.root);   bfw.newLine();
        tree.inorder(tree.root);    bfw.newLine();
        tree.postorder(tree.root);
        bfw.close();
    }

    static class Node {
        char data;
        Node left;
        Node right;

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

    static class Tree {
        Node root;

        void add(char data, char leftData, char rightData) {
            if (root == null) { // 루트가 아직 비어있으면
                root = new Node(data);
                if (leftData != '.') root.left = new Node(leftData);
                if (rightData != '.') root.right = new Node(rightData);
            } else search(root, data, leftData, rightData); // 들어갈 자리를 찾아주자
        }

        void search(Node curNode, char data, char leftData, char rightData) {
            if (curNode == null) return; // 끝까지 왔는데 자리 없으면 종료
            else if(curNode.data == data){
                if (leftData != '.') curNode.left = new Node(leftData);
                if (rightData != '.') curNode.right = new Node(rightData);
            }
            else{
                search(curNode.left, data, leftData, rightData);
                search(curNode.right, data, leftData, rightData);
            }
        }

        void preorder(Node curNode) throws IOException {
            bfw.write(curNode.data+"");
            if(curNode.left!=null)  preorder(curNode.left);
            if(curNode.right!=null) preorder(curNode.right);
        }

        void inorder(Node curNode) throws IOException {
            if(curNode.left!=null)  inorder(curNode.left);
            bfw.write(curNode.data+"");
            if(curNode.right!=null) inorder(curNode.right);
        }

        void postorder(Node curNode) throws IOException {
            if(curNode.left!=null)  postorder(curNode.left);
            if(curNode.right!=null) postorder(curNode.right);
            bfw.write(curNode.data+"");
        }
    }
}

profile
개발 빼고 다 하는 개발자

0개의 댓글