[Programmers] 길 찾기 게임

문제

2019 KAKAO BLIND RECRUITMENT > 길 찾기 게임

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

 

 

아이디어

 

이번 문제는 주어진 정보를 가지고 이진트리 만들 주 아니? 를 물어보는 것 같습니다.

 

왜냐하면 이진 트리를 구성하게 되면 자연스럽게 전위 순회와 후위 순회를 했을 때의 순서를 알 수 있기 때문입니다.

 

이진트리를 만드는 방법은 생각보다 어렵지 않았습니다.

 

주어진 노드 정보들의 y값들이 트리의 depth가 되기 때문에 y값이 큰 순서부터 차례대로 판단을 해주면 됩니다.

 

먼저 y에 대해 오름차순 하면 첫 번째 인덱스 값이 부모 노드가 됩니다.

 

부모 노드를 찾은 후부터는 부모 노드를 시작점으로 하여 인덱스로 나온 노드가 부모의 x값보다 크면 부모의 오른쪽에, 부모의 x값보다 작으면 부모의 왼쪽으로 이동시키면 됩니다.     

 

이동했을 때 나오는 노드를 다시 부모로 지정하여 동일하게 판단을 하고 더 이상 존재하는 노드가 없다면 해당 위치에 인덱스에서 뽑아낸 노드를 배치시키면 됩니다.

 

 

위의 방법으로 이진 트리를 만들게 되면 전위 순회, 후위 순회는 재귀 함수를 이용하여 구하면 됩니다.

 

전위 순회는 "노드 저장 → 왼쪽 노드 재귀 함수 호출 → 오른쪽 노드 재귀 함수 호출"로 구할 수 있고 후위 순회는 "왼쪽 노드 재귀 함수 호출 → 오른쪽 노드 재귀 함수 호출 → 노드 저장"으로 구할 수 있습니다.

 

 

구현 코드 (Java)

 

import java.util.*;

class Solution {
    public int[][] solution(int[][] nodeinfo) {
        List<Node> list = new ArrayList<Node>();
        for(int i=0; i<nodeinfo.length; i++) {
        	list.add(new Node(nodeinfo[i][0], nodeinfo[i][1], i+1));
        }
        
        Collections.sort(list, new Comparator<Node>() { // y값으로 내림차순
        	@Override
        	public int compare(Node o1, Node o2) {
        		return o2.y - o1.y;
        	}
		});
        
        Vertex parent = new Vertex(list.get(0).x, list.get(0).y, list.get(0).index); // 첫 번째 노드정보를 부모로 저장
        
        for(int i=1; i<list.size(); i++) {
        	Node targetNode = list.get(i); // 타겟 노드
        	Vertex targetParent = parent; // 부모가 될 노드
        	
        	while(true) {
        		if(targetParent.x > targetNode.x) { // 부모의 x값이 더 클 경우, 타겟 노드는 부모의 왼쪽에 존재
        			if(targetParent.left == null) { // 왼쪽에 값이 없을 경우 왼쪽에 배치
        				targetParent.left = new Vertex(targetNode.x, targetNode.y, targetNode.index);
        				break;
        			} else { // 왼쪽에 값이 있을 경우 다음 노드를 부모 노드로 저장
        				targetParent = targetParent.left;
        			}
        		}
        		
        		if(targetParent.x < targetNode.x) { // 타겟 노드의 x값이 더 클 경우, 타겟 노드는 부모의 오른쪽에 존재
        			if(targetParent.right == null) { // 오른쪽에 값이 없을 경우 오른쪽에 배치
        				targetParent.right = new Vertex(targetNode.x, targetNode.y, targetNode.index);
        				break;
        			} else { // 오른쪽에 값이 있을 경우 다음 노드를 부모 노드로 저장
        				targetParent = targetParent.right;
        			}
        		}
        	}
        }
        
        List<Integer> preList = new ArrayList<Integer>();
        List<Integer> postList = new ArrayList<Integer>();
        
        getPre(parent, preList);
        getPost(parent, postList);
        
        int res[][] = new int[2][nodeinfo.length];
        for(int j=0; j<nodeinfo.length; j++) {
        	res[0][j] = preList.get(j);
        	res[1][j] = postList.get(j);
        }
    	
        return res;
    }
    
    public void getPre(Vertex edge, List<Integer> preList) { // 전위 순회
    	if(edge == null) {
    		return;
    	}
    	
    	preList.add(edge.index);
    	getPre(edge.left, preList);
    	getPre(edge.right, preList);
    }
    
    public void getPost(Vertex edge, List<Integer> postList) { // 후위 순회
    	if(edge == null) {
    		return;
    	}
    	
    	 getPost(edge.left, postList);
    	 getPost(edge.right, postList);
    	 postList.add(edge.index);
    }
    
    private static class Node { // nodeinfo의 값을 담는 클래스
    	int x, y, index;

		public Node(int x, int y, int index) {
			this.x = x;
			this.y = y;
			this.index = index;
		}
    }
    
    private static class Vertex { // 트리를 구성하는 Vertex 클래스
    	int x, y, index;
    	Vertex left, right;
    	
		public Vertex(int x, int y, int index) {
			this.x = x;
			this.y = y;
			this.index = index;
			this.left = null;
			this.right = null;
		}
    }
}

 

 

 

읽어주셔서 감사합니다.