[BOJ] 백준 2178 JS

백준 / 2178 / JS / BFS

https://www.acmicpc.net/problem/2178

문제

N×M크기의 배열로 표현되는 미로가 있다.

1 0 1 1 1 1
1 0 1 0 1 0
1 0 1 0 1 1
1 1 1 0 1 1
미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

풀이

0,0 위치에서 n,m 위치로 최소경로로 도달할 때 값을 구하기 위해 다음 위치는 현재 위치에서 1을 더한 값이 되기 때문에 다음 위치에 현재 위치까지 이동한 값을 더하면서 최종 위치의 값을 탐색을 마치고 출력한다.

let input = require('fs')
  .readFileSync(__dirname + '/input.txt', { encoding: 'utf-8' })
  .split('\n');
const [n, m] = input.shift().split(' ').map(Number);
const graph = input.map((e) => e.split('').map(Number));
const visited = Array.from(Array(n), () => Array(m).fill(false));
const dy = [-1, 1, 0, 0];
const dx = [0, 0, -1, 1];

const bfs = (y, x) => {
  let queue = [[y, x]];
  while (queue.length) {
    const [cy, cx] = queue.shift();
    for (let i = 0; i < 4; i++) {
      const ny = dy[i] + cy;
      const nx = dx[i] + cx;
      if (ny >= 0 && ny < n && nx >= 0 && nx < m) {
        if (!visited[ny][nx] && graph[ny][nx]) {
          visited[ny][nx] = true;
          // 핵심 : bfs로 탐색하면서 다음 위치의 값은 현재 위치에서 1을 더한 값이 되기 때문에
          // 다음 위치는 현재 위치의 값을 더한 값이 되게 하였다.
          graph[ny][nx] += graph[cy][cx];
          queue.push([ny, nx]);
        }
      }
    }
  }
};

bfs(0, 0);
// 최종 위치에 도달헀을때가 결국 0, 0 에서 시작해서 도착지점까지 1씩 더한 값이 되기때문에 최솟값이 된다.
console.log(graph[n - 1][m - 1]);