The Maze III

유승선 ·2024년 2월 28일
0

LeetCode

목록 보기
108/121

역시 리트코드 하드 문제는 생각을 많이 하게 만든다. 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; 
    }
}
profile
성장하는 사람

0개의 댓글