[algorithm] 백준 2178 - 미로탐색

[문제] 백준 2178 - 미로탐색
[링크] https://www.acmicpc.net/problem/2178
[기본] BFS 탐색
[푸는데 걸린 시간] 약 3시간

let input = require('fs').readFileSync('testcase_04.txt').toString().split('\n');
const [n, m] = input[0].split(' ');

const maze = [];
const mark = [];

for (let i = 0; i < n; i++) {
  maze[i] = [];
  mark[i] = [];
  const tmp = input[i + 1].split('');
  for (let j = 0; j < m; j++) {
    maze[i][j] = +tmp[j];
    mark[i][j] = 0;
  }
}
console.log(maze)

const dx = [1, 0, -1, 0]; // step for direction x
const dy = [0, 1, 0, -1]; // step for direction y

const bfs = () => {
  const queue = [];
  queue.push([0, 0]); // codinate of the start point
  mark[0][0] = 1;

  while(queue.length) {
    const v = queue.shift();
    for (let i = 0; i < 4; i++) {
      let nextV = [v[0] + dy[i], v[1] + dx[i]];
      if (nextV[0] >= 0 && nextV[0] < n && nextV[1] >= 0 && nextV[1] < m) {
        if (nextV[0] === n - 1 && nextV[1] === m - 1) {
          return mark[v[0]][v[1]] + 1;
        }
        if (maze[nextV[0]][nextV[1]] && !mark[nextV[0]][nextV[1]]) {
          queue.push(nextV);
          mark[nextV[0]][nextV[1]] = mark[v[0]][v[1]] + 1;
        }
      }
    }
  }
}

console.log(bfs());

어려웠던 점

1. BFS 레벨링
   문제는 마지막 점에 도착하는데 걸리는 최소 경로의 길이를 구하는 문제이다.
   그렇기 때문에 레벨링을 하면서 탐색을 해야 한다.
   여러 시행착오의 결과 다음과 같은 알고리즘이 좋다는 것을 알았다.
   1) 시작점의 레벨을 1로 정한다. 레벨을 표시할 베열이 필요하다.
   2) 큐에서 한 점 p의 좌표를 꺼내, 그 점으로부터 이동할 수 있는 점들을 찾는다.
   3) 찾은 점들의 레벨 = p의 레벨 + 1
2. 0으로 가득찬 [N x M] 2차원 배열을 만드는 방법
   JavaScript API를 이용해 한 줄에 만드는 방법을 차지 못했다.
   for문을 두 번 돌리면서 그 안에서 0을 주는 방법을 사용했다.
3. 숫자를 나타내는 문자열을 숫자로 바꾸는 새로운 방법을 알았다.
   보통은 Number()를 사용했지만, 이 문제를 풀면서 +연산자를 사용해보았다.

   let a = '123';
   console.log(+a); // 123