코드

function solution(maps) {
  const maxX = maps[0].length-1; // X좌표 끝이자 최종 지점
  const maxY = maps.length-1; // Y좌표 끝이자 최종 지점
  const moveX = [1, -1, 0, 0]; // X좌표 움직이기
  const moveY = [0, 0, 1, -1]; // Y좌표 움직이기
  
  const queue = [[0, 0, 1]]; // [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) => {
	// 초기값인 0과 1에 도달하는 경우
	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];
}

참고 사이트

• https://80000coding.oopy.io/60c3d4d3-f569-4b47-bdde-9a65d30f3bc5