[BaekJoon] 2206 번 벽 부수고 이동하기 문제 - (nodejs)

문제 번호 :  2206

문제 바로가기 ☞ https://www.acmicpc.net/problem/2206

---

 

<<< 문제 내용 >>>

---

 

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\r\n");

const dy = [-1, 1, 0, 0];
const dx = [0, 0, -1, 1];

const [by, bx] = input[0].split(" ").map(Number);
let visited = Array.from(Array(by), () =>
  Array.from(Array(bx), () => new Array(2).fill(0))
);
input.shift();
input.map((el, i) => (input[i] = el.split("")));

const bfs = (cy, cx, breakCnt) => {
  visited[cy][cx][breakCnt] = 1;
  let queue = [[cy, cx, breakCnt]];
  let idx = 0;

  while (idx !== queue.length) {
    [cy, cx, breakCnt] = queue[idx++];

    if (cy === by - 1 && cx === bx - 1) {
      console.log(visited[cy][cx][breakCnt]);
      return;
    }

    for (let i = 0; i < 4; i++) {
      let [ny, nx] = [cy + dy[i], cx + dx[i]];

      if (ny < 0 || ny >= by || nx < 0 || nx >= bx) continue;

      if (visited[ny][nx][breakCnt] === 0) {
        if (input[ny][nx] === "0") {
          visited[ny][nx][breakCnt] = visited[cy][cx][breakCnt] + 1;
          queue.push([ny, nx, breakCnt]);
        } else {
          if (breakCnt === 0) {
            // 만약 벽이고 벽을 안부시고 왔다면
            visited[ny][nx][breakCnt + 1] = visited[cy][cx][breakCnt] + 1;
            queue.push([ny, nx, breakCnt + 1]);
          }
        }
      }
    }
  }

  console.log(-1);
};

bfs(0, 0, 0);

* 방문을 3차원 배열로 선언해주는 센스가 필요했다..

2차원 배열로는 "문을 부수고 가지 않은 세계"와 "문을 부수고 난 이후의 세계"를 구분짓기가 어렵다.

 

✨ [이동 횟수를 세는 방법을 queue에 담는 방법을 사용했었는데

      이 문제는 차원을 구분해서 횟수를 추산해야 하기 때문에, 방문(visited)에 기록해주도록 한다.]

 

이제는 유형을 알았으니.. 비슷한 문제가 나와도 풀 수 있겠지만

구글링 전에는 왜 안되지? 소리가 절로 나왔을 법 한 문제였다.

 

 

 

도움이 되셨다면 공감 부탁드립니다.