2019 카카오 블라인드 코딩테스트 (프로그래머스, Java, 길 찾기 게임)

5. 길 찾기 게임

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/42892

코딩테스트 연습 - 길 찾기 게임 | 프로그래머스

알고리즘 설명:

2진 트리를 만들고 전위, 후위 순회를 하면 되는 문제

• 인덱스와 x, y 좌표, 이진트리의 좌우 노드를 관리하는 Node 클래스를 만들었다.

• y 크기 순으로 정렬을 하고 같은 경우에 x가 작은 순으로 정렬을 하였다.

• 전위 순회 방식으로 root 부터 right, left 노드를 채워갔다.

• 전위 순회와 후위 순회는 list에 넣어주는 타이밍을 바꿔주어 구현하였다.

코드(Java)

import java.util.*;
class Solution {
    public int[][] solution(int[][] nodeinfo) {
		int[][] answer = new int[2][nodeinfo.length];
		Node[] nodeArr = new Node[nodeinfo.length];
		for (int i = 0; i < nodeinfo.length; i++) {
			nodeArr[i] = new Node(nodeinfo[i][0], nodeinfo[i][1], i + 1);
		}

		Arrays.sort(nodeArr, new Comparator<Node>() {
			public int compare(Node n1, Node n2) {
				return n2.y == n1.y ? n1.x - n2.x : n2.y - n1.y;
			}
		});
		Node root = nodeArr[0];
		for (int i = 1; i < nodeArr.length; i++) {
			searchAndInsert(root, nodeArr[i]);
		}
		List<Integer> list = new LinkedList<>();
		
		beforeSearch(root, list);
		for(int i=0;i<list.size();i++) {
			answer[0][i] = list.get(i);
		}
		list.clear();
		afterSearch(root, list);
		for(int i=0;i<list.size();i++) {
			answer[1][i] = list.get(i);
		}
		
		return answer;
	}

	public static void searchAndInsert(Node root, Node insertNode) {
		if (root.x > insertNode.x) {
			if (root.left != null)
				searchAndInsert(root.left, insertNode);
			else {
				root.left = insertNode;
			}
		} else {
			if (root.right != null)
				searchAndInsert(root.right, insertNode);
			else {
				root.right = insertNode;
			}
		}
	}

	public static void beforeSearch(Node root, List<Integer> list) {
		list.add(root.idx);
		
		if (root.left != null)
			beforeSearch(root.left, list);
		
		if (root.right != null)
			beforeSearch(root.right, list);
		
	}
	
	public static void afterSearch(Node root, List<Integer> list) {
		if (root.left != null)
			afterSearch(root.left, list);
		
		if (root.right != null)
			afterSearch(root.right, list);
		list.add(root.idx);
		
	}

	public static class Node {
		int x;
		int y;
		int idx;
		Node left = null;
		Node right = null;

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