BOJ_S1_1991

📁 [S1_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 Main {
	// 왼쪽, 오른쪽 저장 노드
	static class Node{
		int left;
		int right;
		public Node(int left, int right) {
			super();
			this.left = left;
			this.right = right;
		}
	}

	static int N;
	static List<Node>[] list;
	static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		// **** input start ****

		N = Integer.parseInt(br.readLine());

		// ArrayList를 품고있는 list 생성
		list = new ArrayList[N];

		for(int i=0; i<N; i++) {
			list[i] = new ArrayList<>();
		}

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");

			// 0 -> 'A', 1 -> 'B', 2 -> 'C',
			int top = st.nextToken().charAt(0) - 65;
			int left = st.nextToken().charAt(0) - 65;
			int right = st.nextToken().charAt(0) - 65;

			// 리스트에 노드 입력
			list[top].add(new Node(left, right));
		}

		// **** input end ****

		// 전위
		preorder(0);
		sb.append("\n");
		// 중위
		inorder(0);
		sb.append("\n");
		// 후위
		postorder(0);

		System.out.println(sb);
	}

	// 전위 : 루트 -> 왼 -> 오
	static void preorder(int start) {
		for(Node node : list[start]) {
			int left = node.left;
			int right = node.right;

			// 출력
			sb.append((char)(start+'A'));
			// 왼쪽 것이 '.' 이 아닌 경우
			if(left != -19) preorder(left);
			// 오른쪽 것이 '.' 이 아닌 경우
			if(right != -19) preorder(right);
		}
	}

	// 중위 : 왼 -> 루트 -> 오
	static void inorder(int start) {
		for(Node node : list[start]) {
			int left = node.left;
			int right = node.right;

			// 왼쪽 것이 '.' 이 아닌 경우
			if(left != -19) inorder(left);
			// 출력
			sb.append((char)(start+'A'));
			// 오른쪽 것이 '.' 이 아닌 경우
			if(right != -19) inorder(right);
		}
	}

	// 후위 : 왼 -> 오른 -> 루트
	static void postorder(int start) {
		for(Node node : list[start]) {
			int left = node.left;
			int right = node.right;

			// 왼쪽 것이 '.' 이 아닌 경우
			if(left != -19) postorder(left);
			// 오른쪽 것이 '.' 이 아닌 경우
			if(right != -19) postorder(right);
			// 출력
			sb.append((char)(start+'A'));
		}
	}
}

🤔 나의 생각

이 문제를 품으로써 트리 문제 접근에 대해 확실히 깨달았다 키키키
트리 문제에서 가장 중요한 것은 트리 정보에 대한 저장이다.
전위, 중위, 후위 는 재귀를 통해 접근하면 된다는 것을 쉽게 파악할 수 있었지만 트리를 어떻게 저장할 지는 고민이 많았다.
전에 트리 문제와 이번 트리 문제가 동일하게 List[] 배열 안에 ArrayList를 생성해 저장하는 것이다.
그래서 본인과 연결된 모든 노드를 연결하고 나중에 for문을 통해 사용하는 것이다.
풀이 방법은 다음과 같다.

• 노드 클래스를 만들고
• ArrayList를 저장하는 list 배열 생성
• 값들 입력 ( 문자를 숫자로 저장 -> ‘A’ : 0 , ‘B’ : 1 …)
• 전위, 중위, 후위 생성
• ’.’ 을 입력받을 땐 숫자로 -19가 저장됨
• -19이 아니면 계속 재귀로 값 출력해주기