프로그래머스 lv3 길 찾기 게임

문제 링크

길 찾기 게임

풀이

처음에는 DFS 인줄 알았으나, 전위탐색 (preOrder), 후위탐색(postOrder)를 보고 이진탐색트리라는 것을 알았다.

주어진 node 배열을 우선 Node 클래스의 리스트형태로 만든 다음, 노드의 높이 값에 맞게 정렬을 하고 해당 리스트를 이진탐색트리로 만들어준다.

그 다음에는 전위탐색, 후위탐색을 진행하면 되는데 둘 다 왼쪽에서 오른쪽으로 깊이 탐색을 하나 해당 노드의 값을 넣는 위치가 다르다.

import java.util.ArrayList;
import java.util.List;

class Solution {
    private static int index = 0;
	private static int[] preOrder;
	private static int[] postOrder;
    public int[][] solution(int[][] nodeinfo) {
		List<Node> nodeList = new ArrayList<>();
		for (int i = 0; i < nodeinfo.length; i++) {
			nodeList.add(new Node(nodeinfo[i][0], nodeinfo[i][1], i + 1));
		}

		nodeList.sort(
				(a, b) -> {
					if ( a.y == b.y ) {
						return a.x - b.x;
					}
					return b.y - a.y;
				}
		);

		// make tree
		Node root = nodeList.get(0);
		for (int i = 1; i < nodeList.size(); i++) {
			Node node = nodeList.get(i);
			makeTree(root, node);
		}

		// preOrder
		preOrder = new int[nodeinfo.length];
		preOrder(root);
		// postOrder
		index = 0;
		postOrder = new int[nodeinfo.length];
		postOrder(root);

		return new int[][]{preOrder, postOrder};
    }
    
    private static void makeTree(Node parent, Node child) {
		if ( parent.x > child.x ) {
			if ( parent.left == null ) {
				parent.setLeft(child);
			} else {
				makeTree(parent.left, child);
			}
		} else {
			if ( parent.right == null ) {
				parent.setRight(child);
			} else {
				makeTree(parent.right, child);
			}
		}
	}

	private static void preOrder(Node node) {
		if ( node == null ) return;
		preOrder[index++] = node.idx;
		preOrder(node.left);
		preOrder(node.right);
	}

	private static void postOrder(Node node) {
		if ( node == null ) return;
		postOrder(node.left);
		postOrder(node.right);
		postOrder[index++] = node.idx;
	}
}

class Node {
	int x;
	int y;
	int idx;
	Node left;
	Node right;

	public Node(int x, int y, int idx) {
		this.x = x;
		this.y = y;
		this.idx = idx;
	}

	//setLeft
	public void setLeft(Node node) {
		this.left = node;
	}

	//setRight
	public void setRight(Node node) {
		this.right = node;
	}
}