코드
function solution(maps) {
const maxX = maps[0].length-1;
const maxY = maps.length-1;
const moveX = [1, -1, 0, 0];
const moveY = [0, 0, 1, -1];
const queue = [[0, 0, 1]];
while(queue.length) {
const [y, x, move] = queue.shift();
if(x === maxX && y === maxY) return move;
for(let i=0; i<4; i++) {
const newX = x+moveX[i];
const newY = y+moveY[i];
if(newX >= 0 && newX <= maxX && newY >= 0 && newY <= maxY && (maps[newY][newX]===1)) {
queue.push([newY, newX, move+1]);
maps[newY][newX] = 0;
}
}
}
return -1;
}
BFS로 푸는 최단거리
- 최단거리는 BFS로 푼다!!!!!!!!!!!!!!암기암기암기암기
- while 조건으로 queue길이가 0일 때
- 다음으로 지나갈 곳이 없으면 queue.push가 발생하지 않아 queue는 텅텅 비어요
- shift를 이용하면 두 갈래 길이 나와 갈라지더라도 각각 한 번씩 진행돼요!
- 그러다 먼저 도착하는 곳이 있으면 return으로 탈출하기 때문에 최단거리를 구할 수 있어요
- i가 4까지 있는 이유는 네 방향으로 갈 수 있기 때문이에요
BFS는 bottom-up과 top-down
bottom-up(반복문)
- 큰 문제를 풀기 위해 작은 문제부터 접근하여 n에 도달
- 난 이게 더 좋아요~
const bottom_up_fibo = (n) => {
const table = Array(n).fill(0);
table[0] = 1;
table[1] = 2;
for (let i = 2; i < n; i++) {
table[i] = table[i - 1] + table[i - 2];
}
return table[n - 1];
}
top-down(재귀함수)
- n부터 호출하여 fn(0)까지 도달하는 재귀함수
const memo = Array(n + 1).fill(0);
const top_down_fibo = (n) => {
if (n < 2) {
memo[n] = n;
return n;
}
if (memo[n] > 0)
return memo[n];
memo[n] = top_down_fibo(n - 1) + top_down_fibo(n - 2);
return memo[n];
}
참고 사이트