경주로 건설

Solution

0,0 지점에서 N-1, N-1 지점까지 도착할 때 최소비용을 구하는 문제이다.
현재 방향을 그대로 유지하면서 진행할 경우 비용은 +100, 방향을 바꾸는 경우는 +600의 비용이 추가되며, dfs와 bfs 두 가지 모두 풀이가 가능하다.

• DFS
  • 기존 visited 2차원 배열에서 방향성이 추가되므로 3차원배열을 사용
  • visited배열에 이 지점까지 오는 최소 비용을 갱신하면서 가지치기
  • 가지치면서 모든 경우를 탐색하여 최소값을 찾음
• BFS
  • 기존 visited 2차원 배열에서 방향성이 추가되므로 3차원배열을 사용
  • PriorityQueue를 사용하여 비용이 낮은 순서대로 정렬, 가장 먼저 (N-1, N-1) 도달했을 때가 최소비용

  Code

• DFS

import java.util.*;

class Solution {
    class Road{
        int row, col, price, direction;
        
        public Road(int row, int col, int price, int direction){
            this.row = row;
            this.col = col;
            this.price = price;
            this.direction = direction;
        }
    }
    public static int N, minCost;
    public static final int STRAIGHT_PRICE = 100;
    public static final int CORNER_PRICE = 500;
    public static int[][][] visited;
    public static int[] dr = {0, -1, 0, 1};
    public static int[] dc = {-1, 0, 1, 0};
    public int solution(int[][] board) {
        minCost = Integer.MAX_VALUE;
        N = board.length;
        
        // 처음 시작지점에서 아래, 오른쪽으로 진행가능
        visited = makeArr(N);
        dfs(board, new Road(0, 0, 0, 2));
        
        visited = makeArr(N);
        dfs(board, new Road(0, 0, 0, 3));
        
        return minCost;
    }
    
    public void dfs(int[][] board, Road road){
        
        if(road.price >= minCost) return;
        
        if(road.row == N - 1 && road.col == N - 1){
            minCost = Math.min(minCost, road.price);
            return;
        }

        
         for(int i = 0; i < 4; i++){
            int nr = road.row + dr[i];
            int nc = road.col + dc[i];
            
            // 진행하려는 방향이 같지 않으면서, 둘다 홀수 또는 짝수라면 180도 이므로 갈 수 없다
            if(road.direction != i && road.direction % 2 == i % 2) continue;
            int price = roadPrice(road.direction, i);
            
            if(nr < 0 || nr >= N || nc < 0 || nc >= N || board[nr][nc] == 1) continue;
             
            if(road.price + price <= visited[nr][nc][i]){
                visited[nr][nc][i] = road.price + price;
                dfs(board, new Road(nr, nc, road.price + price, i));
             }
        } 
    }
    
    public int roadPrice(int currDir, int nextDir){
        if(currDir == nextDir) return STRAIGHT_PRICE;
        else return CORNER_PRICE + STRAIGHT_PRICE;
    }
    
    public int[][][] makeArr(int n){
        int[][][] arr = new int[n][n][4];
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                for(int k = 0; k < 4; k++){
                    arr[i][j][k] = Integer.MAX_VALUE;
                }
            }
        }
        return arr;
    }
}

• BFS

import java.util.*;

class Solution {
    class Road implements Comparable<Road>{
        int row, col, price, direction;
        
        public Road(int row, int col, int price, int direction){
            this.row = row;
            this.col = col;
            this.price = price;
            this.direction = direction;
        }
        
        @Override
        public int compareTo(Road r){
            return this.price - r.price;
        }
    }
    public static final int STRAIGHT_PRICE = 100;
    public static final int CORNER_PRICE = 500;
    public static int[] dr = {0, -1, 0, 1};
    public static int[] dc = {-1, 0, 1, 0};
    public int solution(int[][] board) {
        int N = board.length;
        int answer = 0;
        
        // visited배열을 가장 큰 정수로 초기화
        int[][][] visited = new int[N][N][4];
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                for(int k = 0; k < 4; k++){
                    visited[i][j][k] = Integer.MAX_VALUE;
                }
            }
        }

        // 처음 가능한 방향은 아래, 오른쪽 2가지
        PriorityQueue<Road> q = new PriorityQueue<>();
        q.offer(new Road(0, 0, 0, 2));
        q.offer(new Road(0, 0, 0, 3));
        
        while(!q.isEmpty()){
            Road road = q.poll();
            
            if(road.row == N - 1 && road.col == N - 1){
                answer = road.price;
                break;
            }
            
            for(int i = 0; i < 4; i++){
                int nr = road.row + dr[i];
                int nc = road.col + dc[i];
                
                if(nr < 0 || nr >= N || nc < 0 || nc >= N || board[nr][nc] == 1) continue;
                
                int price = roadPrice(road.direction, i);
                // 다음 지점의 기록된 최소비용보다, 현재 위치에서 이동하는 비용이 더 싸면 갱신
                if(road.price + price < visited[nr][nc][i]){
                    visited[nr][nc][i] = road.price + price;
                    q.offer(new Road(nr, nc, road.price + price, i));
                }
            }
        }
        return answer;
    }
  
    public int roadPrice(int currDir, int nextDir){
        if(currDir == nextDir) return STRAIGHT_PRICE;
        else return CORNER_PRICE + STRAIGHT_PRICE;
    }
}