공부 204일차: 백준 1991번 트리 순회 자바 java

1991 트리 순회

https://www.acmicpc.net/problem/1991

1991번: 트리 순회

 

 

 

---

백준 1991번 문제 트리 순회

---

문제

---

 

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	128 MB	42275	27619	21077	66.313%

문제

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

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

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

가 된다.

입력

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

출력

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

제한

 

예제 입력 1

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

예제 출력 1

ABDCEFG
DBAECFG
DBEGFCA

힌트

 

 

 

 

---

과정 생각해보기 & 오답

---

 

https://gimbalja.tistory.com/365

전위 순회(preorder), 중위 순회(inorder), 후위 순회(postorder)는 정보처리기사 시험에도 나오는 개념이다

위 포스팅에 어떻게 다른지 적어두었다

 

트리를 구현하는 건 처음이라 고민하다가 검색해보았다

여러 방법이 있었는데, 가장 이해하기 쉬운 블로그가 있었다

 

이후 순회 메서드들은 매우 단순해서 사실 트리 구현만 참고했다고 하면 내가 한 건 없는 수준이긴 하다

 

 

---

정답 인정 코드

---

 

 

import java.io.*;
import java.util.*;
 
public class Main {
 
    static int n;
    static ArrayList<ArrayList<Node>> tree = new ArrayList<>();
    static StringBuilder sb = new StringBuilder();
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        n = Integer.parseInt(br.readLine());
        
        for(int i = 0; i < n; i++) {
            tree.add(new ArrayList<Node>());
        }
        
        for(int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            
            int root = st.nextToken().charAt(0)-'A';
            int left = st.nextToken().charAt(0)-'A';
            int right = st.nextToken().charAt(0)-'A';
            
            tree.get(root).add(new Node(left, right));
        }
        
        preorder(0);
        sb.append('\n');
        inorder(0);
        sb.append('\n');
        postorder(0);
        
        System.out.println(sb.toString());
    }
    
    // 전위 순회
    static void preorder(int start) {
        for(Node n : tree.get(start)) {
            int left = n.left;
            int right = n.right;
            
            sb.append((char)(start+'A'));
            if(left != -19) {    // . : -19
                preorder(left);
            }
            if(right != -19) {    // . : -19
                preorder(right);
            }
        }
    }
    
    // 중위 순회
    static void inorder(int start) {
        for(Node n : tree.get(start)) {
            int left = n.left;
            int right = n.right;
            
            if(left != -19) {    // . : -19
                inorder(left);
            }
            sb.append((char)(start+'A'));
            if(right != -19) {    // . : -19
                inorder(right);
            }
        }
    }
    
    // 후위 순회
    static void postorder(int start) {
        for(Node n : tree.get(start)) {
            int left = n.left;
            int right = n.right;
            
            if(left != -19) {    // . : -19
                postorder(left);
            }
            if(right != -19) {    // . : -19
                postorder(right);
            }
            sb.append((char)(start+'A'));
        }
    }
    
    static class Node{
        int left;
        int right;
        Node(int left, int right){
            this.left = left;
            this.right = right;
        }
    }
 
}
 

 

 

 

---

 

찾아봤을 때 트리 구현 방법이 여러 개라 나중에 한 번 더 풀어볼듯