[프로그래머스] 42892 길 찾기 게임(2019 카카오 블라인드)

1. 문제

https://programmers.co.kr/learn/courses/30/lessons/42892

코딩테스트 연습 - 길 찾기 게임

2. 접근방법

좌표를 보고

이진트리 형태로 만든뒤 전위 순회, 후위 순회를 하는 문제

 

좌표상의 노드들을 이어 이진트리를 만드는 게 문제의 핵심이다.

 

나는 먼저 가장 상위 노드들 부터 나올 수 있도록

Y값을 기준으로 정렬을 하였고

먼저 가장 상위 노드를 X좌표 검사용 리스트에 넣고

하나씩 꺼내서 현재 검사용리스트 상태에서 꺼낸 노드의 위치가 어디인지 찾는다.

 

그림에서 보면 처음 7을 검사용 리스트에 뽑아 넣고

다음 4를 뽑으면 7의 왼편에 있다는 것을 x좌표로 알아낼 수 있다. (x값을 기준으로 이분 탐색하여 찾아낸다.)

2는 오른편에 있다는 것을 알 수 있다.

 

그 다음 1의 위치를 찾으면 4와 7사이 인 것을 알 수 있는데

이때 문제의 제한에 따라 4와 7중 하나는 1의 부모이고 4와 7은 같을 수 없으므로

4와 7중 y값이 더 낮은 곳이 1의 부모가 됨을 알 수 있다.

 

이렇게 이분탐색과 y값을 보고 이진트리를 완성할 수 있다.

 

이후 후위순회와 중위순회를 하여 답을 구하면 된다.

 

---------------------------------

다른 풀이

 

트리를 만들때

분할정복으로 최상위 노드를 기준으로 절반 나누고

나눈것에서 또 최상위 노드를 기준으로 절반 나누는 식으로

리프 노드까지 들어가면 쉽게 트리로 만들 수 있다.

 

3. 자바 코드

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class P42892길찾기게임 {
	class node implements Comparable<node> {
		int num;
		int x;
		int y;
		int left;
		int right;

		@Override
		public int compareTo(node o) {
			return o.y - this.y;
		}

		public node(int num, int x, int y, int left, int right) {
			this.num = num;
			this.x = x;
			this.y = y;
			this.left = left;
			this.right = right;
		}

		public node() {
		}

	}

	// 레벨 순으로 하나씩 뽑기
	// 이분탐색으로 위치 찾기
	// 왼쪽 오른쪽 보고 노드 저장
	//
	List<Integer> preorder;
	List<Integer> postorder;

	public int[][] solution(int[][] nodeinfo) {

		List<node> nodeListLevel = new ArrayList<node>();
		List<node> nodeListNum = new ArrayList<node>();
		List<node> nodeListFind = new ArrayList<node>();
		preorder = new ArrayList<Integer>();
		postorder = new ArrayList<Integer>();
		for (int i = 0; i < nodeinfo.length; i++) {
			node one = new node();
			one.num = i + 1;
			one.x = nodeinfo[i][0];
			one.y = nodeinfo[i][1];
			nodeListLevel.add(one);
			nodeListNum.add(one);
		}

		Collections.sort(nodeListLevel, new Comparator<node>() {
			@Override
			public int compare(node o1, node o2) {
				return o2.y - o1.y;
			}
		});
		Collections.sort(nodeListNum, new Comparator<node>() {
			@Override
			public int compare(node o1, node o2) {
				return o1.num - o2.num;
			}
		});

		nodeListFind.add(new node(-1, -1, 100001, 0, 0));
		nodeListFind.add(nodeListLevel.get(0));
		nodeListFind.add(new node(-1, 1000000, 100001, 0, 0));
		int first = nodeListFind.get(1).num;
		for (int i = 1; i < nodeListLevel.size(); i++) {
			node now = nodeListLevel.get(i);
			int loc = findLoc(nodeListFind, now);
			if (nodeListFind.get(loc).y < nodeListFind.get(loc + 1).y)
				nodeListFind.get(loc).right = now.num;
			else
				nodeListFind.get(loc + 1).left = now.num;
			nodeListFind.add(loc + 1, now);
		}
		getOrder(first, nodeListNum);
		int[][] answer = new int[2][nodeinfo.length];

		for (int i = 0; i < nodeinfo.length; i++) {
			answer[0][i] = preorder.get(i);
			answer[1][i] = postorder.get(i);
		}
		return answer;
	}

	public int findLoc(List<node> nodeListFind, node now) {
		int left = 0;
		int right = nodeListFind.size();

		while (left + 1 < right) {
			int mid = (left + right) / 2;
			if (nodeListFind.get(mid).x > now.x)
				right = mid;
			if (nodeListFind.get(mid).x < now.x)
				left = mid;
		}
		return left;
	}

	public void getOrder(int now, List<node> nodeListNum) {
		preorder.add(now);
		node nowNode = nodeListNum.get(now - 1);
		if (nowNode.left != 0)
			getOrder(nowNode.left, nodeListNum);
		if (nowNode.right != 0)
			getOrder(nowNode.right, nodeListNum);
		postorder.add(now);
	}

}

4. 마치며

다른 풀이들을 보면서 분할정복으로 트리 만드는 것을 보고 감탄했다.

앞으로 트리보면 분할정복부터 생각해봐야겠다.