[Java] BOJ4256, 백준 - 트리

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

4256번: 트리

 

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	192 MB	3081	1562	1189	54.692%

문제

이진 트리는 매우 중요한 기본 자료 구조이다. 아래 그림은 루트 노드가 유일한 이진 트리이다. 모든 노드는 최대 2개의 자식 노드를 가질 수 있으며, 왼쪽 자식이 순서가 먼저이다. 노드 n개로 이루어진 이진 트리를 BT라고 하자. BT의 노드는 1부터 n까지 유일한 번호가 매겨져 있다.

아래 그림에 나와있는 BT의 루트는 3번 노드이다. 1번 노드는 오른쪽 자식만 가지고 있고, 4와 7은 왼쪽 자식만 가지고 있다. 3과 6은 왼쪽과 오른쪽 자식을 모두 가지고 있다. 나머지 노드는 모두 자식이 없으며, 이러한 노드는 리프 노드라고 부른다.

BT의 모든 노드를 순회하는 방법은 전위 순회(preorder), 중위 순회(inorder), 후위 순회(postorder)로 총 세 가지가 있다. 이 세 방법은 아래에 C 스타일의 의사 코드로 나와 있다. BT의 노드 v에 대해서, v.left는 왼쪽 자식, v.right는 오른쪽 자식을 나타낸다. v가 왼쪽 자식이 없으면 v.left는 ∅와 같고, 오른쪽 자식이 없으면 v.right는 ∅와 같다.

BT를 전위 순회, 중위 순회한 결과가 주어진다. 즉, 위의 함수 중 preorder(root node of BT)와 inorder(root node of BT)를 호출해서 만든 리스트가 주어진다. 두 순회한 결과를 가지고 다시 BT를 만들 수 있다. BT의 전위, 중위 순회한 결과가 주어졌을 때, 후위 순회했을 때의 결과를 구하는 프로그램을 작성하시오.

예를 들어, 위의 그림을 전위 순회하면 3,6,5,4,8,7,1,2, 중위 순회하면 5,6,8,4,3,1,2,7이 된다. 이를 이용해 후위 순회하면 5,8,4,6,2,1,7,3이 된다.

 

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 노드의 개수 n이 주어진다. (1 ≤ n ≤ 1,000) BT의 모든 노드에는 1부터 n까지 서로 다른 번호가 매겨져 있다. 다음 줄에는 BT를 전위 순회한 결과, 그 다음 줄에는 중위 순회한 결과가 주어진다. 항상 두 순회 결과로 유일한 이진 트리가 만들어지는 경우만 입력으로 주어진다.

 

출력

각 테스트 케이스마다 후위 순회한 결과를 출력 한다.

 

 

<풀이>

• 전위 순회의 경우 루트 노드 > 왼쪽 노드 > 오른쪽 노드 순으로 방문한다.
• 중위 순회의 경우 왼쪽 노드 > 루트 노드 > 오른쪽 노드 순으로 방문한다.
• 후위 순회의 경우 왼쪽 노드 > 오른쪽 노드 > 루트 노드 순으로 방문한다.

주어진 것은 전위 순회와 중위 순회기 때문에, 이를 가지고 어떻게 노드들을 찾아낼지 생각해보자.

우선 문제의 예제를 루트 노드인 3까지 중위 순회하는 순서를 보도록 하겠다.

클릭하면 움직입니다. 

이처럼 중위 순회 시 루트 노드까지 도달하기까지 루트 노드를 기준으로 왼쪽에 있는 노드들을 우선적으로 방문하게 된다.

즉, 중위 순회의 전체 결과인

5 6 8 4 3 1 2 7

에서 루트 노드인 3 전까지의 노드들은 전부 루트 노드(3)를 기준으로 왼쪽에 있는 노드들이라는 의미가 된다.

5 6 8 4 3 1 2 7

그 다음으로는 3 전까지의 노드들만 확인해보자.

이 서브트리들 또한 같은 매커니즘으로 이해할 수 있다. 중위 순회의 결과인

5 6 8 4

에서 루트 노드인 6 전까지의 노드들은 6을 기준으로 왼쪽, 6 오른쪽의 노드들은 6을 기준으로 오른쪽에 있다.

이렇게 트리를 서브트리로 작게 분할하여 비교해나가면 전체 트리가 어떻게 구성되어 있는지 알 수 있다.

 

+참고로 전위 순회는 루트 노드를 가장 처음으로 방문하기 때문에, 전위 순회의 결과(즉, 루트 노드)를 기준(인덱스)로 해서 중위 순회의 결과들을 분할해주면 된다.

 

그러면 후위 순회 방식인 왼쪽 > 오른쪽 > 루트 순으로 방문하려면 어떡해야할까??

위에서 설명한 방식으로 어디에 어느 노드가 있는지 알아낼 수 있으니, 그러면 루트 노드를 기준으로 모든 노드를 탐색하면서 왼쪽 > 오른쪽 > 노드 출력 순으로 진행하도록 하자

 

 

순서도

1. 트리에서 루트 노드를 찾는다.
2. 서브트리로 나눈 후, 서브트리에서 루트 노드를 찾는다
3. 1, 2번을 반복
4. 리프 노드에 다다르면 출력

소스코드

import java.io.*;
import java.util.*;

public class Main {
	private static int[] preorder;
	private static int[] inorder;
	private static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		// 입력부
		int T = Integer.parseInt(br.readLine());
		for (int t = 0; t < T; t++) {
			int n = Integer.parseInt(br.readLine());
			preorder = new int[n];
			inorder = new int[n];
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int i = 0; i < n; i++)
				preorder[i] = Integer.parseInt(st.nextToken());
			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < n; i++)
				inorder[i] = Integer.parseInt(st.nextToken());

			// 함수 실행
			go(0, n - 1, 0);
			sb.append("\n");
		}
		System.out.println(sb);
	}

	// start, end: 서브 트리의 시작, 끝
	// idx: 루트 노드의 인덱스
	private static void go(int start, int end, int idx) {
		for (int i = start; i <= end; i++) {
			if (inorder[i] == preorder[idx]) { // 트리에서 루트 노드를 찾는다.
				// start와 end값을 루트 노드를 기준으로 쪼개서 서브트리로 나눠준다.

				// 후위 순회 과정(왼>오>방문)
				go(start, i - 1, idx + 1); // 왼
				go(i + 1, end, idx + 1 + i - start); // 오

				// 더이상 재귀로 방문할 곳이 없는 리프 노드에 다다르면
				sb.append(preorder[idx] + " "); // 출력
			}
		}
	}
}

 

+ 참고로 이거는 "후위 순회만을"찾는 알고리즘이 아니라, 중위 순회와 전위 순회의 결과를 이용하여 트리가 뭔지 알 수 있게 해주는 알고리즘이기 때문에, 왼>오>출력의 순서를

출력 > 왼 > 오 로 바꾸면 전위 순회의 결과를,

왼 > 출력 > 오 로 바꾸면 중위 순회의 결과를 얻을 수 있다.

또한 비슷한 맥락으로 중위와 전위가 아니라, 후위+전위, 중위+후위의 결과를 가지고도 트리를 구할수도 있다.