[Programmers] 67259. 경주로 건설 (java)

해당 문제는 bfs와 dp를 함께 사용하여 해결할 수 있습니다.

 

일반적인 bfs문제와 크게 다르지 않지만, 2차원 배열만으로 문제를 해결할 경우 코너에 대한 예외 경우가 너무 많아져 문제를 해결하기 어렵습니다.

 

따라서 height * width * 4 (4는 방향의 수) 크기의 배열을 만들어 방향 별로 가장 비용이 덜 드는 경우를 저장해주면 됩니다. 

 

어떤 지점으로 이동하고자 할 때에 해당 지점의 해당 방향으로 이미 지나간 경로가 있는지를 확인하고, 이미 지나간 경로가 있다면, 해당 경로보다 비용이 적을 경우 큐에 추가해주는 형식으로 해결해 나가시면 됩니다.

 

import java.io.*;
import java.util.*;
 
class Solution {
    public int [][]d = {{-1,0},{0,-1},{1,0},{0,1}};
    public class position{
        int x;
        int y;
        int dir;
        
        public position(int x, int y, int dir){
            this.x = x;
            this.y = y;
            this.dir = dir;
        }
    }
    public Queue<position> q = new LinkedList<>();
    public int answer = Integer.MAX_VALUE;
    
    public void bfs(position p, int [][] board){
        for(int i=0;i<4;i++){
            if(Math.abs(i-p.dir) == 2)
                continue;
            
            int nx = p.x + d[i][0];
            int ny = p.y + d[i][1];
            
            if(nx < 0 || ny < 0 || nx > board.length - 1 || ny > board[0].length - 1 || board[nx][ny] == 1){
                continue;
            }
            
            if(visit[nx][ny][i] == 0){
                if(p.dir != i)
                    visit[nx][ny][i] = visit[p.x][p.y][p.dir] + 600;
                else
                    visit[nx][ny][i] = visit[p.x][p.y][p.dir] + 100;
                q.add(new position(nx, ny, i));   
            }
            else{
                if(p.dir != i){
                    if(visit[nx][ny][i] > visit[p.x][p.y][p.dir] + 600){
                        visit[nx][ny][i] = visit[p.x][p.y][p.dir] + 600;
                        q.add(new position(nx, ny, i));   
                    }
                }
                else{
                    if(visit[nx][ny][i] > visit[p.x][p.y][p.dir] + 100){
                        visit[nx][ny][i] = visit[p.x][p.y][p.dir] + 100;
                        q.add(new position(nx, ny, i));   
                    }
                }
                
            }
            
        }
    }
    
    public int [][][] visit;
    public int solution(int[][] board) {
        visit = new int[board.length][board[0].length][4];
        q.add(new position(0,0,2));
        q.add(new position(0,0,3));
        board[0][0] = 0;
 
        while(!q.isEmpty()){
            position p = q.poll();
            bfs(p, board);
        }
        int min = Integer.MAX_VALUE;
        for(int i = 0;i < 4; i++){
            if(visit[board.length - 1][board[0].length - 1][i] != 0)
                min = Math.min(min, visit[board.length - 1][board[0].length - 1][i]);
        }
        return min;
    }
}