강의로 돌아가기
(!!정답코드포함) JS풀이 (테케25번까지 통과)
해당문제를 풀이하는데 꽤 많은 시간을 쓴 것 같다.
dp와 bfs를 함께 사용해서 풀이를 해야한다.
하지만 테케25번을 통과하기 위해서는 한가지 중요한 포인트가 있다.
2차원 배열 dp를 통해 단순히 x, y 좌표까지의 최소비용으로 구한다면 정답을 구할 수 없다.
그 이유는 해당문제는 방향에 따라서 비용이 달라지기 때문에 특정 좌표까지 최소비용이라도 다음좌표에서 무조건 최소비용을 보장 할 수 없기 때문이다.
따라서 3차원 배열 dp를 통해 방향까지 조건으로 dp풀이를 해야한다.
dp[x좌표][y좌표][방향을 의미하는 index값]으로 정의한다.
dfs를 통해 완전탐색을 수행한 후 dp[N-1][N-1] 중 최소비용을 return하면 모든 case를 통과할 수 있다.
function solution(board) {
const N = board.length;
// DIRECTIONS 배열의 index가 실제 방향을 탐색하는데 쓰이는 값이다. 오/왼/위/아래 -> 0/1/2/3
const DIRECTIONS = [[1, 0], [-1, 0], [0, -1], [0, 1]];
const dp = Array(N).fill().map(() => Array(N).fill().map(() => Array(4).fill(Infinity)));
const isValid = (x, y) => x >= 0 && x < N && y >= 0 && y < N && board[x][y] !== 1;
// 초기값은 0,0에서 오른쪽 / 아래로 이동하는 경우만 지정한다.
const queue = [[0, 0, 0, 0], [0, 0, 0, 3]];
// queue를 사용한 bfs를 수행한다.
while(queue.length) {
const [x, y, cost, dir] = queue.shift();
for(let i = 0; i < DIRECTIONS.length; i++) {
const [mx, my] = DIRECTIONS[i];
const [_x, _y] = [x + mx, y + my];
if(isValid(_x, _y)) {
let new_cost = cost + 100;
// 진행하는 방향과 다른 방향은 회전하는 방향이다.
if(dir !== i) new_cost += 500;
// 되돌아가는 방향의 cost는 무조건 new_cost보다 작기때문에 왔던 방향은 이조건에서 제외된다.
if(new_cost < dp[_x][_y][i]) {
dp[_x][_y][i] = new_cost;
queue.push([_x, _y, new_cost, i]);
}
}
}
}
return Math.min(...dp[N - 1][N - 1]);
}
답변 쓰기