programmers_[카카오 인턴] 경주로 건설_java

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

프로그래머스

import java.util.*;

class Solution {
    private int[][] delta = {{0,1}, {1,0}, {0,-1}, {-1,0}}; // 우 하 좌 상
    public int solution(int[][] board) {
        int answer = 0;
        
        answer = bfs(board);
        
        return answer;
    }
    
    //경로 탐색
    private int bfs(int[][] board){
        int N = board.length;
        int dp[][][] = new int[N][N][4]; // 들어오는 방향별 dp
        
        // 초기값 설정 (0,0)은 우, 하로 들어옴(0,1), (1,0)으로 이동이 직선
        Queue<Road> queue = new LinkedList<>();
        queue.offer(new Road(0,0,0,0)); // 우
        queue.offer(new Road(0,0,1,0)); // 하
        
        while(!queue.isEmpty()){
            Road now = queue.poll();
            
            // 더 적은 값으로 dp값 갱신
            if(dp[now.y][now.x][now.dir] == 0 || dp[now.y][now.x][now.dir] > now.cost){ 
                dp[now.y][now.x][now.dir] = now.cost;
            }else{ // 더 큰값인 경우 무시
                continue;
            }

            // 목적지 도달
            if(now.y == N-1 && now.x == N-1) continue;
            
            // 4방 탐색
            for(int i = 0; i<4; i++){
                int nexty = now.y + delta[i][0];
                int nextx = now.x + delta[i][1];
                // 이동 가능 판단
                if(0<=nexty && nexty < N && 0<=nextx && nextx<N && board[nexty][nextx] == 0){
                    int nextCost = now.cost + calCost(now.dir, i);
                    queue.offer(new Road(nexty, nextx, i, nextCost));
                }
            }
        }
        
        // (N-1, N-1)은 하, 우로만 들어옴 - 둘다 0이 아닌 경우 둘중 최소값
        if(dp[N-1][N-1][0] != 0 && dp[N-1][N-1][1] != 0){
           return Math.min(dp[N-1][N-1][0], dp[N-1][N-1][1]);
        } // 하나라도 0인 경우 큰값
        else{
           return Math.max(dp[N-1][N-1][0], dp[N-1][N-1][1]);
        }        
    }    
    
    
    private int calCost(int dir1, int dir2){
        if(dir1 == dir2){ // 직선도로
            return 100;
        }else{ //직선도로 + 코너
            return 600;
        }
    }
    
    // 테스트용
    private void printMap(int[][][] map){
        for(int i = 0; i<map.length; i++){
            for(int k = 0; k<4; k++){
                for(int j=0; j<map[i].length; j++){                
                    System.out.printf("%3d ", map[i][j][k]);
                }
                System.out.print("| ");
            }            
            System.out.println();
        }
        System.out.println();
    }
    
    private class Road{
        int y, x, dir, cost;
        public Road(int y, int x, int dir, int cost){
            this.y = y;
            this.x = x;
            this.dir = dir;
            this.cost = cost;
        }
    }
}