백준 1991 트리 순회 Java

백준 1991 트리 순회 Java

728x90

solved.ac = 실버 1

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

1. 접근

트리의 개념을 코드로 구현해내는 가장 기본적인 문제가 아닐까 싶다.

자료구조 2번에 트리에 대해서 간단히 정리해두었으니 모르는 분은 한 번 보고 오셔도 될 것 같다!

https://dhbang.tistory.com/14?category=905670

전위, 중위, 후위 순회를 하려면 DFS를 재귀적으로 호출했을 때 스택이 어떻게 쌓이는지 흐름을 따라가봐야 한다.

아래의 전위 순회 코드를 보며 이해해보자.

static void preOrder(int x) { if (x == -1) return; // 현재 노드값 출력 sb.append((char)(x + 'A')); // 왼쪽 자식 호출 preOrder(tree[x][0]); // 오른쪽 자식 호출 preOrder(tree[x][1]); }

코드 순서에 따라 비어있는 값인 -1이면 함수를 종료시키고 그게 아니라면

출력 - 왼쪽 - 오른쪽 순으로 반복하며 뻗어나가게 되는데 위 함수의 실행되는 순서는 아래와 같다.

왼쪽, 오른쪽으로 뻗어 나가는것은 동일하지만 순회 방법에 따라 출력 부분이 코드상 어디에 위치해야 하는지를 생각하며 풀어보자!

2. 풀이

변수 세팅

static int N; static int[][] tree; public static void main(String[] args) throws IOException { N = Integer.parseInt(br.readLine()); tree = new int[26][2]; for (int i = 0; i < N; i++) { st = new StringTokenizer(br.readLine()); // 입력에서 주어지는 대문자 알파벳에서 - A를 빼면 0 ~ 숫자 int parent = st.nextToken().charAt(0) - 'A'; int childX = st.nextToken().charAt(0) - 'A'; int childY = st.nextToken().charAt(0) - 'A'; // 비어있다는 표시인 .이 주어지면 값은 -19가 나온다. tree[parent][0] = (childX == -19) ? -1 : childX; tree[parent][1] = (childY == -19) ? -1 : childY; } solution(); }

순회 및 정답 출력

static void solution() { // 전위 순회 preOrder(0); sb.append('

'); // 중위 순회 inOrder(0); sb.append('

'); // 후위 순회 postOrder(0); System.out.println(sb.toString()); }

각 순회

// 전위 순회 static void preOrder(int x) { if (x == -1) return; // 현재 노드값 출력 sb.append((char)(x + 'A')); // 왼쪽 자식 호출 preOrder(tree[x][0]); // 오른쪽 자식 호출 preOrder(tree[x][1]); } // 중위 순회 static void inOrder(int x) { if (x == -1) return; // 왼쪽 자식 호출 inOrder(tree[x][0]); // 현재 노드값 출력 sb.append((char)(x + 'A')); // 오른쪽 자식 호출 inOrder(tree[x][1]); } // 후위 순회 static void postOrder(int x) { if (x == -1) return; // 왼쪽 자식 호출 postOrder(tree[x][0]); // 오른쪽 자식 호출 postOrder(tree[x][1]); // 현재 노드값 출력 sb.append((char)(x + 'A')); }

3. 전체 코드

from http://dhbang.tistory.com/27 by ccl(A) rewrite - 2021-12-14 11:26:27