[프로그래머스] LV 3 경주로 건설

https://school.programmers.co.kr/learn/courses/30/lessons/67259?language=java

프로그래머스

접근 방법

1. 보드의 크기 n 이 25이하이고 입력에서 걱정할 부분이 없기때문에 BFS를 생각했다.
2. BFS를 하며 Cost를 기록하고, 이를 활용해서 최소값만을 계산하려고했다.
3. 하지만 문제가 있었다.
   1. (1,0)에서 2000코스트이고, (1,1)으로 직진 후 아래로 코너를 돈다
   2. (0,1)에서 1700코스트이고, (1,1)으로 아래로 코너를 돈 후 직진을 한다
   3. 위 두가지 경우에서 1번이 (1,1)에 2100, 2번에 (1,1)이 2400코스트 필요해 1번이 선택된다.
   4. 하지만 그다음 수행까지 고려한다면, 1번은 2700, 2번은 2500 코스트로 2번이 더 최적의 수행이된다.
4. 위 반례를 고려해볼때, 코스트가 500넘게 차이가 나면 서순으로인한 최소값 탈락을 방지할 수 있다.
5. 따라서 기록된 코스트보다 500정도 큰 경우는 q에 넣는다

코드

import java.util.*;
class Solution {
    int n;
    int[] dr = {-1,1,0,0}, dc={0,0,-1,1};
    public int solution(int[][] board) {
        n = board.length;
        Queue<int[]> q = new LinkedList<>();
        int[][] costMap = new int[n][n];
        for(int[] c : costMap) Arrays.fill(c,Integer.MAX_VALUE);
        q.offer(new int[]{0,0,-1,-500});// r,c,dir,cost

        while(!q.isEmpty()){
            int[] cur = q.poll();

            if(cur[0] == n-1 && cur[1] == n-1) continue;
            
            for(int i = 0 ; i < 4 ; i++){
                int nr = cur[0] + dr[i];
                int nc = cur[1] + dc[i];
                int c = cur[2] != i? cur[3]+600 : cur[3]+100;

                if(OOB(nr,nc) || board[nr][nc] == 1 || costMap[nr][nc] < c - 500) continue;
                q.offer(new int[]{nr,nc,i,c});
                costMap[nr][nc] = Math.min(c,costMap[nr][nc]);
            }
        }
        return costMap[n-1][n-1];
    }
    boolean OOB(int r,int c){
        return r < 0 || r >= n || c < 0 || c >= n;
    }
}