[백준/javascript] 2178 미로 (다시 풀기)

const fs = require("fs");
// let stdin = fs.readFileSync("./input.txt").toString();
let stdin = fs.readFileSync("/dev/stdin").toString();
const input = stdin.split("\n").map((v) => v.split(" "));
const [a, ...b] = input;
const [N, M] = a.map(Number);
const miro = b.map((el) => el[0].split("").map(Number));

function bfs(y, x) {
  //bfs로 풀어야 하는 이유
  //가까운 곳부터 먼저 가야하니까!!!
  //y,x를 이동시켜가다가 N-1,M-1인 순간 멈추면됨.
  //이동했을때 +1하고.
  //이동하는 방법은 y+1 y-1하든가 x+1 x-1 하면 됨.
  // bfs니까 갈수있는 곳이 세개가 있다?? 그럼 세개 다가면 됨.
  // 못가는 경우는 miro[y][x]가 0인경우, y가 N보다 크거나 같거나, X가 M보다 크거나 같은 경우, y혹은 x가 0보다 작은 경우
  //나머지는 열심히 가면 됨.!
  const visited = {};
  const queue = [[y, x]];
  let dy = [1, -1, 0, 0]; //상하
  let dx = [0, 0, -1, 1]; //좌우
  let current;
  visited[[y, x]] = 1;
  while (queue.length) {
    //queue안에 있을때만 돌기.
    current = queue.shift(); //queue배열의 앞에서부터 돌기..
    for (let i = 0; i < 4; i++) {
      let y = current[0] + dy[i];
      let x = current[1] + dx[i];
      if (
        y >= 0 &&
        x >= 0 &&
        y < N &&
        x < M &&
        miro[y][x] === 1 &&
        !visited[[y, x]]
      ) {
        queue.push([y, x]);
        visited[[y, x]] = visited[current] + 1; //visited[[y,x]]에는 [y,x]에 오기위해 필요한 최소 이동수가 담긴다.
      }
    }
  }
  return visited[[N - 1, M - 1]];
}

console.log(bfs(0, 0));

정말 어려웠던 ㅎㅎㅎ...

1. 인접한 곳으로 이동하면서 최소거리를 구하는 것이니까 bfs를 이용한다.

2. dy와 dx를 이용해서 갈 수 있는 곳을 확인한다. 즉, 내가 지금 [2,2]의 위치에 있다면 한번의 이동으로 갈수 있는곳은 [1,2] [3,2] [2,1] [2,3]이다. for문을 통해서 이 네개의 좌표를 만든(?) 것이다.

3. 하지만 이 네개의 좌표에서는 갈 수 없는 곳이 있다.(좌표값이 0이거나, 존재하지 않는 좌표라든가... 이미 방문한 좌표라든가.. 최소거리를 구하는 것이기때문에 이미 방문한 좌표는 들르면 안된다.) 그런 곳은 제외하고 나머지 경우에만 방문한다.

4. 이때 queue에 push를 해준다. 처음 좌표 [0,0]에서 포문을 돌면, [0,0]에서 갈 수 있는 좌표만 포문에 추가된다.

5. 앞에서 queue.shift()를 통해 [0,0]은 삭제했으므로 그 다음 좌표부터 열심히 돌아주면 된다.

6. 이때 방문한 곳을 표시를 해줘야 하는데 visited객체에 방문한 좌표를 키, 그 좌표까지 이동하기 위한 이동거리를 값으로 주었다.

7. 이제 열심히 돌고, 마지막에 visited[N-1,M-1]을 반환해주면 된다.