[백준][너비우선탐색] 1261 알고스팟 NodeJs 구현

목차

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

문제

 

 

문제 구현 방향

 아이디어가 필요한 문제였다.

덱을 통해 0이면 앞에 그대로 추가해 주고 1이면 뒤에 1더해서 추가해 준뒤 bfs를 하면 된다.

그렇게 하면 0일때는 다시 그 상태를 유지하고 먼저 탐색하기 때문이다.

 

 

 

코드 구현

const input = require("fs")
  .readFileSync("./dev/stdin", "utf-8")
  .trim()
  .split("\n");

let [M, N] = input[0].trim().split(" ").map(Number);

let board = [];
let dx = [0, 0, 1, -1];
let dy = [1, -1, 0, 0];

let visit = Array.from({ length: N }, () => Array(M).fill(0));

for (let i = 1; i < input.length; i++) {
  board.push(input[i].trim().split("").map(Number));
}

function bfs(x, y) {
  let dequeue = [];
  dequeue.push([x, y, 0]);
  visit[y][x] = 1;
  while (dequeue.length) {
    let t = dequeue.shift();
  
    if (t[0] === M - 1 && t[1] === N - 1) {
      console.log(t[2]);
      return;
    }
    for (let i = 0; i < 4; i++) {
      let nx = t[0] + dx[i];
      let ny = t[1] + dy[i];
      if (nx < 0 || nx > M - 1 || ny < 0 || ny > N - 1) continue;
      if (visit[ny][nx]) continue;
      if (board[ny][nx] === 0) dequeue.unshift([nx, ny, t[2]]);
      else dequeue.push([nx, ny, t[2] + 1]);
      visit[ny][nx] = 1;
    }
  }
}

bfs(0, 0);