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

문제

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

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

문제해결방법

해당 칸 까지의 거리를 저장하는 배열을 가로로 도착했을 때와 세로로 도착했을 때 두 가지 경우로 나눠서 계산해주었다.

또 코너로 꺾이는 부분에서도 직선 도로는 생기므로 코너로 꺾는 부분에서는 600의 코스트를 더해주었다.

코드

package Programmers;
 
import java.util.ArrayDeque;
import java.util.Queue;
 
public class Solution_경주로건설 {
    
    public static int N;
    public static int[][] dir = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};
    public static int[][][] price;
    
    public static void bfs(int[][] board) {
        Queue<int[]> q = new ArrayDeque<int[]>();
        q.add(new int[] {0, 0, 0});
        q.add(new int[] {0, 0, 1});
        price[0][0][0] = 0;
        price[0][0][1] = 0;
        while(!q.isEmpty()) {
            int[] cur = q.poll();
            for(int d=0; d<dir.length; d++) {
                int nx = cur[0] + dir[d][0];
                int ny = cur[1] + dir[d][1];
                if(nx>=0 && nx<N && ny>=0 && ny<N && board[nx][ny]==0) {
                    if(cur[2]==0) {    // 가로
                        if(d<2) { // 가로
                            if(price[nx][ny][0]>price[cur[0]][cur[1]][0]+100) {
                                price[nx][ny][0]=price[cur[0]][cur[1]][0]+100;
                                q.add(new int[] {nx, ny, 0});
                            }
                        } else { // 세로
                            if(price[nx][ny][1]>price[cur[0]][cur[1]][0]+600) {
                                price[nx][ny][1]=price[cur[0]][cur[1]][0]+600;
                                q.add(new int[] {nx, ny, 1});
                            }
                        }
                    } else { // 세로
                        if(d<2) { // 가로
                            if(price[nx][ny][0]>price[cur[0]][cur[1]][1]+600) {
                                price[nx][ny][0]=price[cur[0]][cur[1]][1]+600;
                                q.add(new int[] {nx, ny, 0});
                            }
                        } else { // 세로
                            if(price[nx][ny][1]>price[cur[0]][cur[1]][1]+100) {
                                price[nx][ny][1]=price[cur[0]][cur[1]][1]+100;
                                q.add(new int[] {nx, ny, 1});
                            }
                        }
                    }
                }
            }
        }
    }
    
    public static int solution(int[][] board) {
        N = board.length;
        price = new int[N][N][2];
        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                price[i][j][0] = Integer.MAX_VALUE>>1;
                price[i][j][1] = Integer.MAX_VALUE>>1;
            }
        }
        bfs(board);
        int answer = Math.min(price[N-1][N-1][0], price[N-1][N-1][1]);
        return answer;
    }
    
    public static void main(String[] args) {
        int[][] board = {{0,0,0},{0,0,0},{0,0,0}};
        System.out.println(solution(board));
    }
}

코드에 대한 피드백이나 더 좋은 아이디어는 언제나 환영입니다.