[프로그래머스 lv3] 경주로 건설 - Java

문제링크: https://programmers.co.kr/learn/courses/30/lessons/67259

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

---

문제설명

 

 

 

문제접근

BFS로 풀었습니다.

주의할 점은 어떤 방향으로 이동하냐에 따라 코너가 추가될지, 직선도로만 생길지가 달라지기 때문에 비용을 저장하는 상태공간을 3차원으로 설정해야 합니다([행][열][방향]).

또한, 목표지점 [N-1][N-1] 에 도착하더라도 최소비용임을 보장할 수 없기 때문에 탐색을 종료하지 않고 최솟값만 갱신하여야 합니다.

 

 

소스코드

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
 
class Solution {
    private final byte EAST = 0, SOUTH = 1, WEST = 2, NORTH = 3, ANY = 4;
    private final byte[][] DIRECTION = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
 
    public int solution(int[][] board) {
        int[][][] dist = new int[board.length][board.length][5];
        for(int[][] d: dist)
            for(int [] f: d)
                Arrays.fill(f, Integer.MAX_VALUE);
 
        dist[0][0][EAST] = 0;
        dist[0][0][SOUTH] = 0;
        dist[0][0][WEST] = 0;
        dist[0][0][NORTH] = 0;
        dist[0][0][ANY] = 0;
 
 
        int answer = Integer.MAX_VALUE;
        Queue<int[]> queue = new LinkedList<>();
 
        queue.offer(new int[]{0, 0, 0, ANY});
 
        while(!queue.isEmpty()){
            int now[] = queue.poll();
            int nowRow = now[0], nowCol = now[1], nowCost = now[2], nowdt = now[3];
            if(nowRow == board.length-1 && nowCol == board.length-1)
                answer = Math.min(answer, nowCost);
 
            for(int nextDt = 0; nextDt < DIRECTION.length; nextDt++){
                int nextRow = nowRow + DIRECTION[nextDt][0], nextCol = nowCol + DIRECTION[nextDt][1];
 
                int nextCost = nowdt == nextDt || nowdt == ANY ? 100 : 600;
 
                if(isBuilt(nextRow, nextCol, board)){
                    if(dist[nextRow][nextCol][nextDt] < dist[nowRow][nowCol][nowdt] + nextCost)
                        continue;
                    dist[nextRow][nextCol][nextDt] = dist[nowRow][nowCol][nowdt] + nextCost;
                    queue.offer(new int[] {nextRow, nextCol, dist[nextRow][nextCol][nextDt], nextDt});
                }
            }
        }
        return answer;
    }
 
    public boolean isBuilt(int row, int col, int[][] board){
        if(row < 0 || board.length <= row || col < 0 || board.length <= col)
            return false;
 
        if(board[row][col] == 1)
            return false;
 
        return true;
    }
}