The Maze III

역시 리트코드 하드 문제는 생각을 많이 하게 만든다. ldru 방향으로 최소 거리를 찾는 문제인데 예전에 카카오 코딩테스트 문제가 생각났다.

비슷한 결의 문제 같긴해서 다음에 시간 내서 풀어볼 예정이다. C++ 로도 똑같은 로직을 적용해서 풀어봤는데 내꺼는 잘 안되어서 결국 해답을 보고 제출 했다.

너무 많은 시간을 사용한거 같은데 그래도 전체적인 흐름을 적용해보면은 다익스트라를 적용 해야한다.

하지만, 다익스트라의 커스텀 조건에 하나를 더 추가해야하는데 최소한의 거리 + 가장 빠른 알파벳 순서를 적용시켜서 Priority Queue 의 순서를 유지 해야했다.

PQ의 활용도가 객체랑 합쳐지면 꽤 높은거같아서 자주 사용하게 된다.

class State{
    int row; 
    int col;
    int dist; 
    String path; 

    public State(int row, int col, int dist, String path){
        this.row = row;
        this.col = col; 
        this.dist = dist; 
        this.path = path;  
    }
}


class Solution {
    int[][] directions = new int[][]{{0,-1},{-1,0},{0,1},{1,0}}; 
    String[] textDirections = new String[]{"l","u","r","d"}; 

    int m; 
    int n; 

    public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
        m = maze.length; 
        n = maze[0].length; 
        PriorityQueue<State> heap = new PriorityQueue<>((a,b) -> {
            int distA = a.dist;
            int distB = b.dist; 

            if(distA == distB){
                return a.path.compareTo(b.path); 
            }

            return distA - distB; 
        });

        boolean[][] seen = new boolean[m][n]; 
        heap.add(new State(ball[0], ball[1], 0, "")); 

        while(!heap.isEmpty()){
            State curr = heap.remove(); 

            int row = curr.row; 
            int col = curr.col; 


            if(seen[row][col]){
                continue; 
            }

            if(row == hole[0] && col == hole[1]){
                return curr.path; 
            }

            seen[row][col] = true; 

            for(State nextState: getNeighbors(row, col, maze, hole)){
                int nextRow = nextState.row; 
                int nextCol = nextState.col;  
                int nextDist = nextState.dist; 
                String nextChar = nextState.path; 
                heap.add(new State(nextRow, nextCol, curr.dist + nextDist, curr.path + nextChar)); 
            }
        }

        return "impossible"; 
    }

    private boolean valid(int row, int col, int[][] maze){
        if(row < 0 || row >= m || col < 0 || col >= n){
            return false; 
        }

        return maze[row][col] == 0; 
    }

    private List<State> getNeighbors(int row, int col, int[][] maze, int[] hole){
        List<State> neighbors = new ArrayList<>(); 

        for(int i = 0; i < 4; i++){
            int dy = directions[i][0]; 
            int dx = directions[i][1]; 

            String direction = textDirections[i]; 
             
            int currRow = row; 
            int currCol = col; 
            int dist = 0; 

            while(valid(currRow + dy, currCol + dx, maze)){
                currRow += dy; 
                currCol += dx; 

                dist++; 

                if(currRow == hole[0] && currCol == hole[1]){
                    break; 
                }
            }

            neighbors.add(new State(currRow, currCol, dist, direction)); 
        }
        return neighbors; 
    }
}