[프로그래머스] Level3 - 길 찾기 게임

package level3;

import java.util.*;

public class Solution_길찾기게임 {
	public static void main(String[] args) {
		String s = "[[5,3],[11,5],[13,3],[3,5],[6,1],[1,3],[8,6],[7,2],[2,2]]";
		s = s.replace("[", "{");
		s = s.replace("]", "}");
		System.out.println(s);
		int[][] nodeinfo = { { 5, 3 }, { 11, 5 }, { 13, 3 }, { 3, 5 }, { 6, 1 }, { 1, 3 }, { 8, 6 }, { 7, 2 },
				{ 2, 2 } };
		System.out.println(solution(nodeinfo));
	}

	static class Pos {
		int n, x, y, min, max;
		Pos left, right;

		public Pos(int n, int x, int y) {
			this.n = n;
			this.x = x;
			this.y = y;
		}

		@Override
		public String toString() {
			return "[" + n + ":" + x + "," + y + "]";
		}

	}

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

		Queue<Pos> pq = new PriorityQueue<>(new Comparator<Pos>() {
			@Override
			public int compare(Pos o1, Pos o2) {
				if (o1.y - o2.y < 0)
					return 1;
				else if (o1.y - o2.y > 0)
					return -1;
				else {
					return o1.x - o2.x;
				}
			}
		});
		Queue<Pos> qu = new LinkedList<>();				// Queue는 parent가 될 노드를 임시저장하는 공간으로, child와 연결할 수 있게 하기 위한 리스트입니다.
	
		int x, y;
		for (int i = 0; i < nodeinfo.length; i++) {
			x = nodeinfo[i][0];
			y = nodeinfo[i][1];
			pq.add(new Pos(i + 1, x, y));
		}

		Pos root = pq.poll();
		root.min = 0;
		root.max = Integer.MAX_VALUE - 1;
		qu.add(root);
		while (!pq.isEmpty()) {
			Pos parent = qu.poll();
			if (parent.y != pq.peek().y && pq.peek().x < parent.x && pq.peek().x < parent.x
					&& pq.peek().x >= parent.min) {
				Pos left = pq.poll();
				left.min = parent.min;
				left.max = parent.x;
				parent.left = left;
				qu.add(left);
			}
			if (pq.isEmpty())
				break;
			if (parent.y != pq.peek().y && pq.peek().x > parent.x && pq.peek().x <= parent.max
					&& pq.peek().x > parent.x) {
				Pos right = pq.poll();
				right.min = parent.x;
				right.max = parent.max;
				parent.right = right;
				qu.add(right);
			}
		}
		preFuc(root);
		answer[0] = preorder;
		index = 0;
		postFuc(root);
		answer[1] = postorder;

		return answer;
	}

	static int[] preorder, postorder;
	static int index;

	static void preFuc(Pos root) {
		preorder[index++] = root.n;
		if (root.left != null) {
			preFuc(root.left);
		}
		if (root.right != null) {
			preFuc(root.right);
		}

	}

	static void postFuc(Pos root) {
		if (root.left != null) {
			postFuc(root.left);
		}
		if (root.right != null) {
			postFuc(root.right);
		}
		postorder[index++] = root.n;
	}
}