[프로그래머스/42892/JAVA] 길 찾기 게임

2019 KAKAO BLIND RECRUITMENT 문제

날짜	분류	번호	알고리즘 분류
21-03-29	프로그래머스	42892	트리, 재귀	링크

문제 요약

1. 트리를 구성하는 노드들이 2차원 좌표 위에 주어졌을 때 전위 순회, 후위 순회한 결과를 반환
2. 규칙
   • 모든 노드는 서로 다른 x값을 가짐
   • 자식 노드의 y 값은 항상 부모 노드보다 작음
   • 모든 노드는 왼쪽 서브 트리에 있는 노드들의 x값보다 작음

 

풀이

1. pq에 Node를 row순, col순으로 정렬하여 넣음
2. pq에서 하나씩 빼면서 tree에 넣음
3. 트리가 완성되면 재귀를 통해 탐색함

 

비고

• 설마 이게 되겠어? 했는데 됐다 우하하

 

package KakaoBlindRecruitment2019.P42892_길찾기게임;

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;

public class Solution {

	static public int[][] solution(int[][] nodeinfo) {
		int[][] answer = new int[2][nodeinfo.length];

		Queue<Node> que = new PriorityQueue<>();
		for (int i = 0; i < nodeinfo.length; i++) {
			que.add(new Node(nodeinfo[i][1], nodeinfo[i][0], i + 1));
		}

		Node root = que.poll();
		while (!que.isEmpty()) {
			root.add(que.poll());
		}

		List<Integer> pre = new ArrayList<>();
		preorder(root, pre);
		for (int i = 0; i < pre.size(); i++) {
			answer[0][i] = pre.get(i);
		}
		List<Integer> post = new ArrayList<>();
		postorder(root, post);
		for (int i = 0; i < post.size(); i++) {
			answer[1][i] = post.get(i);
		}
		return answer;
	}

	private static void postorder(Node node, List<Integer> post) {
		if (node.left != null)
			postorder(node.left, post);
		if (node.right != null)
			postorder(node.right, post);
		post.add(node.no);
	}

	private static void preorder(Node node, List<Integer> pre) {
		pre.add(node.no);
		if (node.left != null)
			preorder(node.left, pre);
		if (node.right != null)
			preorder(node.right, pre);
	}

	static class Node implements Comparable<Node> {
		Node left, right;
		int r, c, no;

		public Node(int r, int c, int no) {
			super();
			this.r = r;
			this.c = c;
			this.no = no;
		}

		public void add(Node input) {
			if (this.c > input.c) {
				if (this.left == null)
					this.left = input;
				else
					this.left.add(input);
			} else {
				if (this.right == null)
					this.right = input;
				else
					this.right.add(input);
			}
		}

		@Override
		public String toString() {
			return "Node [r=" + r + ", c=" + c + ", no=" + no + "]";
		}

		@Override
		public int compareTo(Node o) {
			if (this.r == o.r)
				return this.c - o.c;
			return o.r - this.r;
		}
	}

	public static void main(String[] args) {
		int[][] nodeinfo = { { 5, 3 }, { 11, 5 }, { 13, 3 }, { 3, 5 }, { 6, 1 }, { 1, 3 }, { 8, 6 }, { 7, 2 },
				{ 2, 2 } };
		int[][] result = solution(nodeinfo);
		for (int[] is : result) {
			for (int i : is) {
				System.out.print(i);
			}
			System.out.println();
		}
	}
}