[알고리즘풀이]백준 1991 : 트리 순회 JAVA

목차

• 개요
•  본문
•  1) 문제
•  2) 과정
•  3) 코드 전체

 

 

개요

이번에 알고리즘 스터디에서 JAVA를 이용해 백준 1991번 트리 순회를 풀었습니다. 이를 정리해보고자 합니다.

1697번: 숨바꼭질

 

본문

1) 문제

2) 과정

이번 문제는 한 30분? 걸렸던 것 같아요!! 에러도 한번 안나고 바로 통과해서 기분좋았습니다.ㅎㅎㅎㅎ 금광캐다가 오랜만에 tree로 바뀌면서 실버로 오니 좀 더 빠르게 풀 수 있더라고요!!! 뭐랄까 그동안 레벨 맞춰서 오르비스가고 루디브리움 가다가 오랜만에 헤네시스 온 기분이랄까요!! 그리고 이전에 학교에서 수업들을 땐 이해가 안되던게 오랜만에 푸니까 이렇게 쉽게 생각나고 풀리는게 너무 신기했어요 ㅋㅋㅋㅋㅋㅋ 역시 알고리즘 문제는 풀수록 늘어나는게 맞나봐요 :) 

 

돌아와서, 제가 이번에 풀었던 방식을 후딱 설명드리고 물러나겠습니다.

이번 문제는 DFS방식으로 순서만 바꿔서 풀었어요. 문제에도 써있듯 왼쪽, 오른쪽, 본인의 출력 순서만 적당히 바꿔주면 되더라고요! 자세한건 코드를 보시면 바로 이해하실 겁니다! preorder함수와 inorder, postorder 모두 순서만 조금 바꿔준게 전부였어요!!

 

2-1) main

// Variable
    private static int n;
    // Main
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        
        // Initialize 
        Node[] orgArr = new Node[n];
        char al = 'A';
        for(int i=0;i<n;i++) orgArr[i] =  new Node(al++);
        // Input 
        for(int i=0;i<n;i++){
            char[] line = br.readLine().toCharArray();
            orgArr[line[0]-65].left = line[2]=='.'? null : orgArr[line[2]-65];
            orgArr[line[0]-65].right = line[4]=='.'? null : orgArr[line[4]-65];
        }
        
        // Logic
        // preorder
        System.out.println(preorder(orgArr[0]));
        // inorder
        System.out.println(inorder(orgArr[0]));
        // postorder 
        System.out.println(postorder(orgArr[0]));
        
    }

저는 삼항연산자를 몹시 좋아합니다.. if문으로 같은 값을 줘야하는거면 삼항연산자로 짧게 적는게 더 깔끔해보이더라고요. 아직 올리진 않았지만 삼항연산자 범벅으로 4개?5개를 연결한 것도 있어요 ㅋㅋㅋㅋㅋ

 

무튼 Main은 n을 입력받아 노드의 수를 입력받고, orgArr에 char는 숫자로 바꾸면 A가 65,B가66, C가67... 이렇게 인식된다는 점을 활용하여 Node를 넣어줬습니다. Node클래스는 아래 참고해주세요! (이렇게 글로 쓰니까 굳이 Node를 만들어야했나 생각이 드네요...?! 그래도 가시성은 Node가 int[]보단 좋으니까.. 만족하겠습니다...) 넣어준 노드를 입력에 맞춰 left, right를 설정하며 Input 부분은 끝이납니다.

 

그리고 Logic이자 바로 Output까지 해내는 3개의 순회 함수를 부르며 Main은 종료됩니다.

 

2-2) preorder

    private static String preorder(Node node){
        String retVal = "";
        retVal += node.self;
        if(node.left != null) retVal += preorder(node.left);
        if(node.right != null) retVal += preorder(node.right);
        return retVal;
    }

앞에서 말씀드린대로 각 함수는 순서 차이밖에 없는데요! preorder는 자신을 입력하고, 좌측노드를 담은 뒤, 우측노드를 입력한 값을 리턴하며 끝납니다.

 

2-3) inorder

    private static String inorder(Node node){
        String retVal = "";
        if(node.left != null) retVal += inorder(node.left);
        retVal += node.self;
        if(node.right != null) retVal += inorder(node.right);
        return retVal;    
    }

inorder는 좌측노드를 담아오고, 자신을 입력하고, 우측노드를 입력한 값을 리턴하며 끝이 납니다

 

2-4) postorder

    private static String postorder(Node node){
        String retVal = "";
        if(node.left != null) retVal += postorder(node.left);
        if(node.right != null) retVal += postorder(node.right);
        retVal += node.self;
        return retVal;    
    }

postorder는 좌측노드를 담아오고, 우측노드를 담아온 뒤 자신을 입력한 값을 리턴하며 끝납니다.

 

2-5) Node

    private static class Node{
        char self;
        Node left, right;
        public Node(char self){
            this.self = self;
        }
        public String toString(){
            return self+"";
        }
    }

Node클래스는 자신의 값과 좌측 자식 노드, 우측 자식 노드를 담기 위해 만들어졌습니다. toString은 Object클래스로부터 오버라이드한 함수로 자신의 값을 출력합니다. 저 비어있는 쌍따옴표는 Stirng으로 만들어 리턴해주고자 추가했습니다. 이렇게 정리하려고 코드를 적으니 Node라는 클래스를 만들지말고 int[]에 {본인값, 왼쪽번호, 오른쪽번호}를 저장하게 했으면 이전보다 속도가 더 빨랐을까 생각이 드네요!

 

3) 전체코드

그렇게 완성된 코드는 다음과 같습니다.

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

public class Main {
    // Variable
    private static int n;
    // Main
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        
        // Initialize 
        Node[] orgArr = new Node[n];
        char al = 'A';
        for(int i=0;i<n;i++) orgArr[i] =  new Node(al++);
        // Input 
        for(int i=0;i<n;i++){
            char[] line = br.readLine().toCharArray();
            orgArr[line[0]-65].left = line[2]=='.'? null : orgArr[line[2]-65];
            orgArr[line[0]-65].right = line[4]=='.'? null : orgArr[line[4]-65];
        }
        
        // Logic
        // preorder
        System.out.println(preorder(orgArr[0]));
        // inorder
        System.out.println(inorder(orgArr[0]));
        // postorder 
        System.out.println(postorder(orgArr[0]));
        
    }
    // Method - 본-좌-우
    private static String preorder(Node node){
        String retVal = "";
        retVal += node.self;
        if(node.left != null) retVal += preorder(node.left);
        if(node.right != null) retVal += preorder(node.right);
        return retVal;
    }
    // Method - 좌-본-우
    private static String inorder(Node node){
        String retVal = "";
        if(node.left != null) retVal += inorder(node.left);
        retVal += node.self;
        if(node.right != null) retVal += inorder(node.right);
        return retVal;    
    }
    // Method - 좌-우-본
    private static String postorder(Node node){
        String retVal = "";
        if(node.left != null) retVal += postorder(node.left);
        if(node.right != null) retVal += postorder(node.right);
        retVal += node.self;
        return retVal;    
    }
    // Inner Class - 본인값, 좌측 자식, 우측 자식을 저장하고자 만든 클래스
    private static class Node{
        char self;
        Node left, right;
        public Node(char self){
            this.self = self;
        }
        public String toString(){
            return self+"";
        }
    }
}

 

소요시간, 아이디어, 에러로그 등 더 자세히 이번 문제를 보고싶으시다면, 아래 깃헙 링크를 참고해주세요 :)

https://github.com/Park1122/Algorithm-Study/blob/master/sujeong/tree/BOJ1991.java

GitHub - Park1122/Algorithm-Study: 명지대학교 학생들이 모여서 만든 알고리즘 공부 및 코딩테스트 준비