사용한 것
풀이 방법
- 코너 건설을 구현하기 위해
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;
}
}