[java 백준] 실버 1/ 1991번 트리 순회

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
 
public class Main2 {
    static class Node {
        int left;
        int right;
 
        public Node(int left, int right) {
            this.left = left;
            this.right = right;
        }
    }
 
    static List<Node>[] list;
    static StringBuilder sb = new StringBuilder();
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        int n = Integer.parseInt(br.readLine());
        list = new ArrayList[n + 1];
        for (int i = 0; i < n; i++) {
            list[i] = new ArrayList<>();
 
        }
        for (int i = 0; i < n; i++) {
            String[] line = br.readLine().split(" ");
 
            int data = line[0].charAt(0) - 'A';
            int left = line[1].charAt(0) - 'A';
            int right = line[2].charAt(0) - 'A';
            list[data].add(new Node(left, right));
 
        }
 
        preOrder(0);
        sb.append("\n");
        inOrder(0);
        sb.append("\n");
        pastOrder(0);
        sb.append("\n");
        System.out.println(sb.toString());
 
    }
 
    public static void preOrder(int x) {
        for (Node node : list[x]) {
            int l = node.left;
            int r = node.right;
 
            sb.append((char) (x + 'A'));
            if (l != -19)
                preOrder(l);
            if (r != -19)
                preOrder(r);
        }
    }
 
    public static void inOrder(int x) {
        for (Node node : list[x]) {
            int l = node.left;
            int r = node.right;
 
            if (l != -19)
                inOrder(l);
            sb.append((char) (x + 'A'));
            if (r != -19)
                inOrder(r);
        }
    }
 
    public static void pastOrder(int x) {
        for (Node node : list[x]) {
            int l = node.left;
            int r = node.right;
 
            if (l != -19)
                pastOrder(l);
 
            if (r != -19)
                pastOrder(r);
 
            sb.append((char) (x + 'A'));
        }
    }
 
}
 

 

문제 풀이 

 

우선 나는 배열로 푸는게 더 직관적이여서 배열로 풀었다. (그릿속의 헤빗님 블로그를 참고했다)

 

Node 클래스를 만들고 , 생성자에 lefr,right 변수를 넣어준다. 이후 노드가 추가 될 때 노드의 좌우에  node.left,node.right 를 하나의 배열에 집어 넣는게 

https://we1cometomeanings.tistory.com/170?category=958599 

[java 백준]실버 1/2178번 미로찾기

여타 다른 bfs 문제 풀이와 아이디어가 굉장히 비슷했다.(2178번도 Dote 클래스를 만들고 생성자에 x,y 정해준다. 이후 큐에 x,y 한 세트로 해서 넣어준다. )

 

List와 ArrayList의 차이 

https://yoon-dailylife.tistory.com/7

JAVA) List 와 ArrayList 차이

위 사이트에 자세히 설명되어 있는데

List 가 ArrayList보다 더 유연하다. 광범위한 느낌인 것 같다.

위 글에서 

 

List는 도형 list= new 정사각형();

ArrayList는 정사각형 ArrayList = new 정사각형();

이라는 비유를 하셨는데, 가장 직관적인 비유인 것 같다!

 

 

ArrayList<Node>[]list=new ArrayList[n+1];

 

이렇게 하면 ArrayList에서 할 수 없었던 list[i]=i; 이런식의 선언이 가능하다.

근데 ArrayList에 대괄호가 오는 건 처음봤고, 배열(array)처럼 크기도 제한적으로 설정할 수 있었다.

뿐만아니라 Node [] list= new [n+1] 도 아니고 ArrayList<Node>[]list=new ArrayList[n+1] 이라는게 그냥

신기했다. ArrayList 랑 대괄호가 오는게 타입설정하는 부분 <> 도 아니고 그 뒤에 온다는게 신기해서 스택 오버플로우를 찾아봤다. 보통 <> 안에 [] 가 들어가는 경우는 arraylist안에 array를 넣는 경우인데, 내가 찾고 있는 건 array 안에 arraylist에 해당했다.. ㅜ 열심히 이유를 찾고 있는데, 만약 찾으면 다시 이곳에 적으러 오겠다!

 

 

우선 이 코드를 사용하면

 

1. ArrayList가 아닌 배열 인덱스를 사용해서 배열안에 객체를 넣을 수 있고

2. ArrayList에 크기를 설정할 수 있으며, 배열처럼 사용할 수 있다. 이러면 걍 Node []list=new Node[n+1]; 을 하지 그랬느냐? 하겠지만

 

나중에 전위,중위,후위 순회 메서드를 만들 때

 

for(Node node:list[x]{

} 를 꼭 돌려줘야 하기 때문에 어쩔 수 없다. 

이걸 array로 하게되면 iterable하지 않다고 에러가 뜬다. 그래서 iterable한 List를 쓸 수 밖에..ㅜ

https://girawhale.tistory.com/17

[Java] Iterable과 Iterator

 

 

 

 

참고 사이트

 

 

https://minhamina.tistory.com/80

[Java] 트리(tree) 구현 - 1차원 배열 / 2차원 배열 / 클래스 3가지 방법 구현

https://loosie.tistory.com/344

[BOJ] 백준 1991번 트리 순회 (Java)

 

 

이밖에도 다른 풀이

 

https://minhamina.tistory.com/78

[백준 - Java] 1991번 : 트리 순회

https://velog.io/@jini_eun/%EB%B0%B1%EC%A4%80-1991%EB%B2%88-%ED%8A%B8%EB%A6%AC-%EC%88%9C%ED%9A%8C-Java-Python

[백준] 1991번 트리 순회 / Java, Python

 

--> 처음엔 Node 형 변수 만들어서 풀었는데 나중에 형변환 하는 것 땜에 골머리를 앓아서 이렇게 풀진 않았다 (아마 내가 잘못 풀었을 거다)  이 풀이도 언젠가 유용해질 시점이 올 것 같은 느낌이 들기에 첨부해뒀다.

 

https://dos-soles.tistory.com/15

[BOJ] 1991 트리 순회 - Java

--> 배열로 푼 또 다른 풀이