[CodeKata] Week3 - Day3 (BFS)

문제

양수로 이루어진 m x n 그리드를 인자로 드립니다. 상단 왼쪽에서 시작하여, 하단 오른쪽까지 가는 길의 요소를 다 더했을 때, 가장 작은 합을 찾아서 return 해주세요.

한 지점에서 우측이나 아래로만 이동할 수 있습니다.

Input:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]

Output: 7
Input:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]

Output: 7

설명: 1→3→1→1→1 의 합이 제일 작음

풀이

• 모든 경로를 탐색하여야 하기 때문에 bfs 를 활용하여 풀이하였습니다.
• 2차원 배열, direct 배열, bfs의 이해가 필요합니다.
• 현재 갈 수 있는 경로를 기록하여 최종 목적지에 도착하였을 때 최소 경비를 찾습니다.

코드

const minPathSum = grid => {
  let direct= [[0,1],[1,0]];

  let head =0, tail = 1;
  let queue = [{x:0, y:0, sum:grid[0][0], level:0}];// 시작점을 기록
  let minCost = 999;
  
  let m = grid.length;
  let n = grid[0].length;

  while (head!==tail) {
    let now = queue[head++];
    for (let t=0; t<2; t++) {
      // 최종목적지 도달
      if (now.x === m-1 && now.y === n-1) {
        if (minCost > now.sum) {
          minCost = now.sum;
        }
      }
      
      let dx = now.x + direct[t][0];
      let dy = now.y + direct[t][1];
      if (dx < 0 || dy < 0|| dx >= m || dy >= n) continue;
     queue[tail++] = {x:dx, y:dy, sum:now.sum+grid[dx][dy], level:now.level + 1};
    }
  }
  return minCost;
  
};