[프로그래머스 / Level3] 경주로 건설 (Java)

문제 보기

사용한 것

• 최소 비용으로 경주로를 건설하기 위한 BFS

풀이 방법

• 코너 건설을 구현하기 위해 int[n][n][4] cost (0 : U, 1 : R, 2 : D, 3 : L) 로 선언하고 MAX_VALUE로 초기화한다. (출발점은 0으로)
• BFS를 돌면서 방향을 전환하는 경우(출발점 제외)는 현재 비용에 600을 더하고, 방향을 이어가는 경우는 100을 더한다.
• cost보다 더 작은 비용일때만 q에 넣고 갱신한다.

코드

class Solution {

    private static final int[] DX = {-1, 0, 1, 0};
    private static final int[] DY = {0, 1, 0, -1};
    private int[][] board;
    private int[][][] cost;
    private int n;

    public int solution(int[][] board) {
        init(board);
        return findMinCost();
    }

    private void init(int[][] board) {
        this.board = board;
        n = board.length;
        cost = new int[n][n][4];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                Arrays.fill(cost[i][j], Integer.MAX_VALUE);
            }
        }
        Arrays.fill(cost[0][0], 0);
    }

    private int findMinCost() {
        int minCost = Integer.MAX_VALUE;
        Queue<Point> q = new LinkedList<>();
        q.offer(new Point(0, 0, -1, 0));
        while (!q.isEmpty()) {
            Point cp = q.poll();
            if (isGoal(cp.x, cp.y)) {
                minCost = Math.min(cp.c, minCost);
            }
            for (int i = 0; i < 4; i++) {
                int nx = cp.x + DX[i];
                int ny = cp.y + DY[i];
                int nc;
                if (cp.d == -1 || cp.d == i) {
                    nc = cp.c + 100;
                } else {
                    nc = cp.c + 600;
                }
                if (isOOB(nx, ny) || !isMinCost(nx, ny, i, nc)) {
                    continue;
                }
                q.offer(new Point(nx, ny, i, nc));
                cost[nx][ny][i] = nc;
            }
        }
        return minCost;
    }

    private boolean isGoal(int x, int y) {
        return x == n - 1 && y == n - 1;
    }

    private boolean isOOB(int x, int y) {
        return x < 0 || x >= n || y < 0 || y >= n || board[x][y] == 1;
    }

    private boolean isMinCost(int x, int y, int i, int c) {
        return c < cost[x][y][i];
    }
}

class Point {

    public int x, y, d, c;

    public Point(int x, int y, int d, int c) {
        this.x = x;
        this.y = y;
        this.d = d;
        this.c = c;
    }
}