(백준) 트리 _ 4256

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

 

🐢 설명

어떤 트리가 존재한다고 하였을 때, pre-order, in-order 순서로 방문한 결과를가지고 post-order 순서로 방문했을 때의 결과를 반환해야 하는 문제이다.

 

먼저 pre, in 결과를 가지고 트리를 만들고, post 방식으로 방문한 결과를 반환하도록 하면 되겠다.

 

그럼 pre와 in의 조회 방식 차이를 봐보자.

pre-order

• 현재 방문한 노드의 값을 출력 -> left를 체크, 존재하면 left 방문 ->  right를 체크, 존재하면 right 방문
  하는 방식으로 이뤄진다. 즉, 처음에 방문하는 노드가 루트임이 보장된다.

in-order 

• 현재 방문한 노드 left 체크, 존재하면 방문 -> left 방문 후 현재 방문한 노드 값 출력 -> right 체크, 존재하면 right 방문
  하는 방식이다. 어떤 노드를 방문한다면 왼쪽을 전부 방문 후 자신을 방문하고 오른쪽에 위치한 모든 노드를 방문하게 된다.

그럼 위 방문의 특성을 이용해서 두번째 예제로 트리를 만들어보자.

 

우리가 궁금한건 어떤 노드를 방문했을 때 애가 left인지 right인지 모른다는 건데, 이부분을 in-order의 특징을 이용해서 풀 수 있다. 먼저 pre-order 방식에서 방문한 순서대로 노드들을 이용해서 추적해보자.

 

이때 중요한것은 현재 노드의 왼쪽을 이어서 추적할 때, 해당 노드들이 오른쪽으로 가질 수 있는 최대 노드는 현재노드 미만이라는 것이다. 따라서 현재노드의 위치이하로만 탐색할 수 있게 해줘야 한다.

오른쪽 노드들은 자신이 현재 가지는 오른쪽으로의 최대값과 동일하다. 따라서 오른쪽 탐색으로는 한계선이 변동이 없다. 

 

이렇게 pre order 순서대로 노드를 방문하고 in order를 통해 해당 노드가 왼쪽에 가지는 자식 개수, 오른쪽에 가지는 자식 개수를 세서 leaf인지 다음 노드가 left인지, right인지 정해줄 수 있다.

 

🐢코드

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

public class Main {
	static int T;
	static int N;
	static Node root;
	static boolean[] isUsed;
	static HashMap<Integer, Integer> map;
	static Queue<Integer> preOrderQ = new LinkedList<>();
	static StringBuilder answer = new StringBuilder();

	public static void main(String[] args) throws Exception {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    StringTokenizer st;

		T = Integer.parseInt(br.readLine());
		while (T-- > 0) {
			N = Integer.parseInt(br.readLine());
			map = new HashMap<>();
			preOrderQ.clear();
			isUsed = new boolean[N + 1];

			// pre-order 노드 순서대로 담기
			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < N; i++) {
				int v = Integer.parseInt(st.nextToken());
				preOrderQ.add(v);
			}

			// in-order 노드들의 위치
			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < N; i++) {
				int v = Integer.parseInt(st.nextToken());
				map.put(v, i);
			}

			// 0. 최초 탐색하는 노드 범위는 노드의 개수인 N개이다.
			root = new Node(0, null, null);
			makeTree(root, N);
			dfs(root);
			answer.append("\n");
		}
		System.out.print(answer);
	}

	private static void dfs(Node tree) {
		if (tree.left != null)
			dfs(tree.left);
		if (tree.right != null)
			dfs(tree.right);
		answer.append(tree.value).append(" ");
	}

	private static void makeTree(Node root, int max) {
		if (preOrderQ.isEmpty()) return;

		// 1. 현재 노드를 방문하고, in-order의 위치를 얻는다.
		int cur = preOrderQ.poll();
		int curdex = map.get(cur);

		// 2. 현재 위치의 사용 여부를 체크하고, 값을 적는다.
		isUsed[curdex] = true;
		root.value = cur;

		int left = 0;
		int right = 0;
        // 3. 현재 노드의 왼쪽에 방문하지 않은 노드의 개수를 센다.
		for (int i = curdex - 1; i >= 0; i--) {
			if (!isUsed[i]) left++;
			else break;
		}
        // 4. 현재 노드가 오른쪽으로 가질 수 있는 최대 노드를 센다.
		for (int i = curdex + 1; i < max; i++) {
			right++;
		}

		// 5. 왼쪽 노드가 있다면 해당 노드를 만들어서 이어서 탐색한다.
		if (left != 0) {
			root.left = new Node(-1, null, null);
			makeTree(root.left, curdex);
		}
		// 6. 오른쪽 노드가 있다면 해당 노드를 만들어서 이어서 탐색한다.
		if (right != 0) {
			root.right = new Node(-1, null, null);
			makeTree(root.right, max);
		}
	}

	private static class Node {
		int value;
		Node left;
		Node right;

		public Node(int value, Node left, Node right) {
			this.value = value;
			this.left = left;
			this.right = right;
		}
	}
}

🐢 마무리