경주로 건설

• 문제

https://programmers.co.kr/learn/courses/30/lessons/67259

코딩테스트 연습 - 경주로 건설

• 코드

import java.util.*;

class Solution {
    
    class Pair{
        int row;
        int col;
        int prevDir;
        int curVal;
        public Pair(int row, int col, int prevDir, int curVal){
            this.row = row;
            this.col = col;
            this.prevDir = prevDir;
            this.curVal = curVal;
        }
    }
    
    private final int mv[][] = {
        {-1,0},
        {0,1},
        {1,0},
        {0,-1}
    };
    
    private void printArr(int[][] prev){
        int N = prev.length;
        System.out.println();
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                System.out.print(prev[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println();
    }

    private void bfs(int[][] board, int[][] his){
        int N = board.length;
        Queue<Pair> q = new LinkedList<>();
        q.add(new Pair(0,0,-1,0));
        his[0][0] = 0;
        while(q.size() != 0){
            Pair curNode = q.poll();
            int c_r = curNode.row;
            int c_c = curNode.col;
            int prev_dir = curNode.prevDir;
            int c_v = curNode.curVal;
            for(int i=0; i<4; i++){
                int n_r = c_r + this.mv[i][0];
                int n_c = c_c + this.mv[i][1];
                int n_v = c_v;
                if(prev_dir != -1 && prev_dir != i)
                    n_v += 600;
                else
                    n_v += 100;
                if(N <= n_r || n_r < 0 || N <= n_c || n_c < 0)
                    continue;
                else if(board[n_r][n_c] == 1)
                    continue;
                else if(his[n_r][n_c] < n_v)
                    continue;
                q.add(new Pair(n_r,n_c,i,n_v));
                his[n_r][n_c] = n_v;
            }
        }
    }
    
    public int solution(int[][] board) {
        int answer = 0;
        int N = board.length;
        int prev[][] = new int[N][N];
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                prev[i][j] = 2000000000;
            }
        }
        
        this.bfs(board, prev);
        // this.printArr(prev);
        
        answer = prev[N-1][N-1];
        
        return answer;
    }
}

• 피드백
  • 1시간 20분 걸림
  • 처음에 dfs로 했다가  실패 총 625칸
  • 다음에 dp로 하려고 했으나 설계가 안됨
  • 그 후 bfs로 했으나 실패
  • 최단거리가 아닌 코너 + 직선 값으로 인한 총 비용 값으로 his를 구성했어야함
  • his를 비용의 최솟값으로 하니 통과