경주로 건설

도면의 상태(0은 비어 있음, 1은 벽)을 나타내는 2차원 배열 board가 매개변수로 주어질 때, 경주로를 건설하는데 필요한 최소 비용을 return 하도록 solution 함수를 완성해주세요.
[제한사항]
board는 2차원 정사각 배열로 배열의 크기는 3 이상 25 이하입니다.
board 배열의 각 원소의 값은 0 또는 1 입니다.
도면의 가장 왼쪽 상단 좌표는 (0, 0)이며, 가장 우측 하단 좌표는 (N-1, N-1) 입니다.
원소의 값 0은 칸이 비어 있어 도로 연결이 가능함을 1은 칸이 벽으로 채워져 있어 도로 연결이 불가능함을 나타냅니다.
board는 항상 출발점에서 도착점까지 경주로를 건설할 수 있는 형태로 주어집니다.
출발점과 도착점 칸의 원소의 값은 항상 0으로 주어집니다.

문제는 탐색해서 최소값을 찾는문제 최소값을 찾기에 dfs는 모든 노드를 순회하기위해 만들어졌으므로 임의의 경로를 찾는 bfs가 더 적합하다.
또한 이전값을 기준으로 다음값을 구해야 하기때문에 DP가 필요하다.
또한 방향에따라서 꺾이면 600원 아니라면 100원이기 때문에 이전 방향에 따라서 다음 값이 변한다.
따라서 3차원 배열이 필요함

코드

import java.util.*;
class Solution {
    public int solution(int[][] board) {
        int[][][] cost = new int[4][board.length][board.length];
        int[] dx= {1,-1,0,0};
        int[] dy= {0,0,1,-1};
        for(int i=0;i<4;i++){
            for(int j=0;j<board.length;j++){
                Arrays.fill(cost[i][j],Integer.MAX_VALUE);
            }
        }                                            
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{0,0,0,0});
        queue.add(new int[]{0,0,0,2});
        while(!queue.isEmpty()){
            int[] idx = queue.poll();
            for(int i=0;i<4;i++){
                int nx = dx[i]+idx[1];
                int ny = dy[i]+idx[0];
                int value = idx[2] + (idx[3]==i ? 100:600);
                if(nx<0||ny<0||nx>=board.length||ny>=board.length||cost[i][ny][nx]<value||board[ny][nx]==1) continue;
                cost[i][ny][nx]= value;
                queue.add(new int[]{ny,nx,value,i});
            }
        } 
        int answer=Integer.MAX_VALUE;
        for(int i=0;i<4;i++){
            answer=Math.min(answer,cost[i][board.length-1][board.length-1]);
        }
        return answer;
    }
}//dp문제+ dfs bfs 둘다 가능 하지만..

문제는 이렇게 풀었을시 최악의 경우(가장 마지막으로 오는 값이 최선일 경우) 모든 경로를 순회한다는것이다. 결국 우리가 알아야하는것은 가장 적은 값이니 우선순위 큐를 사용한다면 예의 것을 방지할수 있다.
개선된 우선순위 큐

 Queue<int[]> queue = new PriorityQueue<>(new Comparator<int []>() {
				@Override
				public int compare(int[] o1, int[] o2) {
				
					return o1[2]-o2[2];
				}
			 });

value의 값이 idx[2]이므로 다음과 같이 우선순위큐를 잡아주면 된다.