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

문제 링크

• 길 찾기 게임

풀이

• 좌표 압축과 재귀 함수를 사용하여 해결하였다. 그 후 다른 풀이를 보니 노드와 노드를 연결하는 방식으로 훨씬 간편하게 푼 것을 보고 다음에는 해당 방식으로 풀어보자는 생각을 하였다.
• x와 y좌표가 최대 100,000까지 가능하지만 nodeinfo는 10,000이하로 입력된다. 트리의 깊이는 최대 1,000이하인 경우만 입력으로 들어온다. 해당 조건을 보고 좌표 압축을 한다면 x는 10,000 이하, y는 1000 이하로 정의할 수 있다는 생각을 하였다.
• 압축한 좌표값에 맞는 이차원 배열을 구한 후 부모 노드와 자식 노드의 연결은 재귀함수로 실현하였다.

코드

import java.util.*;

class Solution {
    int height = 0, width = 0;
    int[][] nodeList;
    ArrayList<Integer> prefixList = new ArrayList<>();
    ArrayList<Integer> postfixList = new ArrayList<>();
    
    public int[][] solution(int[][] nodeInfo) {
        int[][] answer = {};
        if (nodeInfo.length == 1) {
            return new int[][] {{1}, {1}};
        }
        
        compress(nodeInfo);
        
        nodeList = new int[height][width];
        int index = 1;
        for (int[] node : nodeInfo) {
            nodeList[node[1]][node[0]] = index++;
        }
        
        dfs(0, width - 1, height - 1);
        
        answer = new int[2][width];
        for (int i = 0; i < width; i++) {
            answer[0][i] = prefixList.get(i);
            answer[1][i] = postfixList.get(i);
        }
        
        return answer;
    }
    
    private void dfs(int x1, int x2, int y) {
        if (y == -1) {
            return;
        }
        
        int x = x1;
        for (; x <= x2; x++) {
            if (nodeList[y][x] != 0) {
                prefixList.add(nodeList[y][x]);
                break;
            }
        }
        
        if (x - 1 >= x1) {
            dfs(x1, x - 1, y - 1);
        }
        
        if (x + 1 <= x2) {
            dfs(x + 1, x2, y - 1);
        }
        
        postfixList.add(nodeList[y][x]);
    }

    private void compress(int[][] nodeInfo) {
        ArrayList<Integer> xList = new ArrayList<>();
        ArrayList<Integer> yList = new ArrayList<>();
        
        for (int[] node : nodeInfo) {
            xList.add(node[0]);
            yList.add(node[1]);
        }
        
        ArrayList<Integer> uniqueXList = new ArrayList<>(new HashSet<>(xList));
        ArrayList<Integer> uniqueYList = new ArrayList<>(new HashSet<>(yList));
        
        Collections.sort(uniqueXList);
        Collections.sort(uniqueYList);
        
        height = uniqueYList.size();
        width = uniqueXList.size();
        
        for (int[] node : nodeInfo) {
            node[0] = uniqueXList.indexOf(node[0]);
            node[1] = uniqueYList.indexOf(node[1]);
        }
    }
}