https://changhyun.vercel.app/80f2257a90614951bd23675a3a3f28e9
-
과거 풀이
function solution(board) { const ans = []; let answered = false; const visited = { h: Array(board.length).fill(0).map(row=>Array(board.length).fill(0)), v: Array(board.length).fill(0).map(row=>Array(board.length).fill(0)) } const isVisited = (x,y,dir) => visited[dir][y][x]; const isSafe = (x,y) => { if(board[y]===undefined){ return false; } const point = board[y][x]; if(point===undefined || point===1){ return false; } return true; } const stack = []; const start = [[1,0,'h','h',100],[0,1,'v','v',100]]; start.forEach(point => isSafe(...point) && stack.push(point)); while(stack.length){ const node = stack.shift(); const [x,y,dir,initDir,cost] = node; if(x===board.length-1 && y===board.length-1){ ans.push(cost); answered = true; } if(isVisited(x,y,initDir)){ if(cost > visited[initDir][y][x]){ continue; } } visited[initDir][y][x] = cost; const nodesBefore = []; const nodesAfter = []; const right = [x+1,y, 'h', initDir]; const left = [x-1,y, 'h', initDir]; const top = [x,y-1, 'v', initDir]; const bottom = [x,y+1, 'v', initDir]; isSafe(...right) && (dir==='h' ? nodesBefore.push([...right, cost+100]) : nodesAfter.push([...right, cost+600])); isSafe(...left) && (dir==='h' ? nodesBefore.push([...left, cost+100]) : nodesAfter.push([...left, cost+600])); isSafe(...top) && (dir==='v' ? nodesBefore.push([...top, cost+100]) : nodesAfter.push([...top, cost+600])); isSafe(...bottom) && (dir==='v' ? nodesBefore.push([...bottom, cost+100]) : nodesAfter.push([...bottom, cost+600])); stack.push(...nodesBefore, ...nodesAfter); } return Math.min(...ans) } -
제출한 풀이
function solution(board) { let answer = Infinity const size = board.length const dx = [0,0,1,-1] const dy = [-1,1,0,0] const isBound = (x,y) => x >= 0 && x < size && y >=0 && y < size const isWall = (x,y) => board[y][x] const costs = { h: Array(size).fill(0).map(c => Array(size).fill(0).map(c => Infinity)), v: Array(size).fill(0).map(c => Array(size).fill(0).map(c => Infinity)) } const stack = [[0,0, null, 0]] while(stack.length){ const [x,y, dir, cost] = stack.shift() if(y === size -1 && x === size -1){ answer = Math.min(answer, cost) continue; } for(let i=0; i<4; i++){ const xx = x + dx[i] const yy = y + dy[i] if(!isBound(xx,yy) || isWall(xx, yy)){ continue; } const newDir = dx[i] === 0 ? 'v' : 'h' const pay = ( dir === null || dir === newDir ) ? 100 : 600 const newCost = cost + pay if(costs[newDir][yy][xx] <= newCost){ continue; } costs[newDir][yy][xx] = newCost stack.unshift([xx, yy, newDir, newCost ]) } } return answer; }
예전에 풀었보았던 문제입니다.
과거 풀이에 첨부했습니다. (이게 더 빠르네요..😅)
더 빠른 이유는 복합적이겠지만
dx dy 를 사용하지 않아 배열을 참조하는 비용이 없고
bfs를 돌릴 때 100원이 더해지는 위치 먼저 스택에 입력했기 때문일 것 같습니다.
최소 비용을 확인하는 것과
두 방향을 나눠 생각하는 과정에서
오랜 시간을 할애했습니다.
풀이 과정
제출한 코드를 요약하면 다음과 같습니다.
- 경로 문제에 필요한 변수/helper 작성
- BFS
1. 경로 문제에 필요한 변수/helper 작성
- isBound : board 안에 포함되는지 확인
- isWall : 벽인지 확인
- minCosts : 다음 depth를 search할 것인지 확인할 때 필요한 기록지 ( 2. 참조 )
const size = board.length
const dx = [0,0,1,-1]
const dy = [-1,1,0,0]
const isBound = (x,y) => x >= 0 && x < size && y >=0 && y < size
const isWall = (x,y) => board[y][x]
// minCosts는 2.BFS 에서 수정됩니다.
const minCosts = Array(size).fill(0).map(c => Array(size).fill(0).map(c => Infinity))2. BFS (breadth first search)
-
아래 표현되는 stage에 대한 설명입니다.
대부분의 문제는 이론적만 생각해본다면 BFS와 DFS 두 방법으로 해결 가능합니다.
이 문제 또한 이론적으로는 BFS , DFS가 가능하기에
제 경우에는 minCosts를 생각하는 과정이 어려웠습니다.
좌표에 대한 가중치가 없는 일반적인 bfs, dfs 경로 문제의 경우
visited 기록지를 이용해 방문했던 위치인지 확인하고
방문한 위치일 경우 다음 stage를 search하지 않는 방식으로 searching이 진행됩니다.
하지만 이 문제의 경우
방문했던 위치인지 아닌지가 다음 stage search의 판별 기준이 아니라,
search할 좌표에 기록되어있는 비용이 최소인지 아닌지가 판별 기준이 됩니다.
즉, 좌표를 search할 때 기록지에 해당 좌표의 최소 비용을 최신화해두고
dx dy 로 사방에 대해 다음 stage를 search할 지를 판별할 때 이를 사용합니다.
다음 stage를 search할 지를 판별하는 과정은 다음과 같습니다.
유효 좌표인지, 벽이 아닌지 확인하고
기록지에 기록된 최소 비용과 예상 비용을 비교해서
예상 비용이 작을 경우 다음 depth search를 진행하고
예상 비용이 클거나 같을 경우에는 다음 depth search를 진행하지 않습니다.
만약 예상 비용이 작은 경우라면 기록지를 예상 비용(최소비용)으로 갱신합니다.
지금까지의 내용을 토대로 코드를 작성해보겠습니다.
const stack = [[0, 0, null, 0]] // x, y, 방향, 비용
while(stack.length){
const [x,y, dir, cost] = stack.shift() // search
if(y === size -1 && x === size -1){ // 도착지에 이를 경우
// 최소 정답 갱신 후 다음 stage search 진행 X
answer = Math.min(answer, cost)
continue;
}
for(let i=0; i<4; i++){ // 사방에 대해
const xx = x + dx[i]
const yy = y + dy[i]
// 다음 stage를 search할 것인지 판별
// 유효한 좌표인지 확인
if(!isBound(xx,yy) || isWall(xx, yy)){
continue;
}
const newDir = dx[i] === 0 ? 'v' : 'h'
const pay = ( dir === null || dir === newDir ) ? 100 : 600
const newCost = cost + pay
// 예상 비용이 최소 비용보다 크거나 같을 경우 다음 stage를 search하지 않습니다.
if(minCosts[yy][xx] <= newCost){
continue;
}
// 예상 비용이 작거나 같은 경우라면 다음 stage를 search해줍니다.
minCosts[yy][xx] = newCost
stack.unshift([xx, yy, newDir, newCost ])
}
}여기까지 작성하게 되면, 3번 케이스를 통과하지 못 하는데요.
차가 바라보는 방향을 고려하지 못 했기 때문입니다.
어떤 좌표의 예상 비용이 최소 비용이 아니더라도, 차가 바라보는 방향에 따라 다음 stage의 search에서 다른 좌표를 최소 비용으로 갱신할 수 있기 떄문입니다.
따라서 한 좌표의 최소 비용을 두 방향으로 분류해줬습니다.
***const minCosts = {
h: Array(size).fill(0).map(c => Array(size).fill(0).map(c => Infinity)),
v: Array(size).fill(0).map(c => Array(size).fill(0).map(c => Infinity))
}***
const stack = [[0,0, null, 0]]
while(stack.length){
const [x,y, dir, cost] = stack.shift()
if(y === size -1 && x === size -1){
answer = Math.min(answer, cost)
continue;
}
for(let i=0; i<4; i++){
const xx = x + dx[i]
const yy = y + dy[i]
if(!isBound(xx,yy) || isWall(xx, yy)){
continue;
}
const newDir = dx[i] === 0 ? 'v' : 'h'
const pay = ( dir === null || dir === newDir ) ? 100 : 600
const newCost = cost + pay
** *if(minCosts[newDir][yy][xx] <= newCost){
continue;
}
minCosts[newDir][yy][xx] = newCost***
stack.unshift([xx, yy, newDir, newCost ])
}
}