백준 1991번: 트리순회 [JAVA]

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

1991번: 트리 순회

• 풀이

우선, tree[N][3] 배열에 입력값(뿌리 알파벳, 왼쪽 자식 알파벳, 오른쪽 자식 알파벳)을 받아주었다.

각각의 순회 함수에서는 자식이 ‘.’이 아니라면, 자식의 알파벳이 뿌리 알파벳인 tree 배열을 찾아 순회를 반복한다. 자식이 하나도 없는 경우 재귀는 종료된다.

전위 순회 : 1. 뿌리 노드 출력 → 2. 왼쪽 자식 탐색 → 3. 오른쪽 자식 탐색 순으로 재귀 함수를 작성한다.

중위 순회 : 1. 왼쪽 자식 탐색 → 2. 뿌리 노드 출력 → 3. 오른쪽 자식 탐색 순으로 재귀 함수를 작성한다.

후위 순회 : 1. 왼쪽 자식 탐색 → 2. 오른쪽 자식 탐색 → 3. 뿌리 노드 출력 순으로 재귀 함수를 작성한다.

• 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static int N;
	static char tree[][];
	
	// 전위 순회
	static void preorder_traverse(int node) {
		// 뿌리 노드 출력
		System.out.print(tree[node][0]);
		
		// 왼쪽 자식 노드 방문
		if(tree[node][1]!='.') {
			for (int i=0; i<N; i++) {
				if (tree[node][1]==tree[i][0]) preorder_traverse(i);
			}
		}
		
		// 오른쪽 자식 노드 방문
		if(tree[node][2]!='.') {
			for (int i=0; i<N; i++) {
				if (tree[node][2]==tree[i][0]) preorder_traverse(i);
			}
		}
	}
	
	// 중위 순회
	static void inorder_traverse(int node) {
		// 왼쪽 자식 노드 방문
		if(tree[node][1]!='.') {
			for (int i=0; i<N; i++) {
				if (tree[node][1]==tree[i][0]) inorder_traverse(i);
			}
		}
		// 뿌리 노드 출력
		System.out.print(tree[node][0]);
		
		// 오른쪽 자식 노드 방문
		if(tree[node][2]!='.') {
			for (int i=0; i<N; i++) {
				if (tree[node][2]==tree[i][0]) inorder_traverse(i);
			}
		}
	}
	
	// 후위 순회
	static void postorder_traverse(int node) {
		// 왼쪽 자식 노드 방문
		if(tree[node][1]!='.') {
			for (int i=0; i<N; i++) {
				if (tree[node][1]==tree[i][0]) postorder_traverse(i);
			}
		}
		// 오른쪽 자식 노드 방문
		if(tree[node][2]!='.') {
			for (int i=0; i<N; i++) {
				if (tree[node][2]==tree[i][0]) postorder_traverse(i);
			}
		}
		// 뿌리 노드 출력
		System.out.print(tree[node][0]);
	}

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		
		// 노드 개수 입력
		N = Integer.parseInt(st.nextToken());
		tree = new char [N][3];
		
		// 노드 입력
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(bf.readLine());
			tree[i][0] = st.nextToken().charAt(0);
			tree[i][1] = st.nextToken().charAt(0);
			tree[i][2] = st.nextToken().charAt(0);
		}
		
		preorder_traverse(0); // 전위순회
		System.out.println();
		inorder_traverse(0); // 중위순회
		System.out.println();
		postorder_traverse(0); // 후위순회
	}
}

• 풀이 2

위의 코드는 tree 배열을 N만큼 만들어서 매번 자식과 같은 문자의 알파벳을 찾아갔다.

이번 코드는 tree 배열을 알파벳 개수인 26개 만큼 만들어서 각 알파벳에 대치되는 인덱스에 자식을 입력한다. 이렇게 되면 자식 노드를 찾을 때 한번에 찾아갈 수 있다.

• 코드 2

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	static int N;
	static int tree[][];
	
	// 전위 순회
	static void preorder_traverse(int node) {
		if (node == -19) return; // '.'인 경우 종료
		System.out.print((char)(node+65)); // 노드 출력
		preorder_traverse(tree[node][0]); // 왼쪽 자식 순회
		preorder_traverse(tree[node][1]); // 오른쪽 자식 순회
	}
	
	// 중위 순회
	static void inorder_traverse(int node) {
		if (node == -19) return; // '.'인 경우 종료
		inorder_traverse(tree[node][0]); // 왼쪽 자식 순회
		System.out.print((char)(node+65)); // 노드 출력
		inorder_traverse(tree[node][1]); // 오른쪽 자식 순회
	}
	
	// 후위 순회
	static void postorder_traverse(int node) {
		if (node == -19) return; // '.'인 경우 종료
		postorder_traverse(tree[node][0]); // 왼쪽 자식 순회
		postorder_traverse(tree[node][1]); // 오른쪽 자식 순회
		System.out.print((char)(node+65)); // 노드 출력
	}

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		
		// 노드 개수 입력
		N = Integer.parseInt(st.nextToken());
		tree = new int [26][2];
		
		// 노드 입력
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(bf.readLine());
			int idx = (int)st.nextToken().charAt(0) - 65;
			tree[idx][0] = (int)st.nextToken().charAt(0) - 65;
			tree[idx][1] = (int)st.nextToken().charAt(0) - 65;
		}
		
		preorder_traverse(0); // 전위순회
		System.out.println();
		inorder_traverse(0); // 중위순회
		System.out.println();
		postorder_traverse(0); // 후위순회
	}
}

• BFS

위의 세가지 함수는 DFS이다. Queue를 이용한 BFS도 구현해보았다.

// BFS
static void BFS (int root) {
	Queue <Integer> que = new ArrayDeque<>();
	que.add(root); // 루트 노드 enqueue
		
	while(!que.isEmpty()) { // 큐가 빌 때까지
		int node = que.poll(); // dequeue
		if (node==-19) continue; // '.'이면 종료
		System.out.print((char)(node+65));
		que.add(tree[node][0]); // 왼쪽 자식 enqueue
		que.add(tree[node][1]); // 오른쪽 자식 enqueue
	}
}