[백준] 3055 탈출 - javascript

📌 문제

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

📌 풀이

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

const [row, col] = input.shift().split(' ').map(Number);
const arr = input.map((i) => i.trim().split(''));
const visited = Array.from({ length: row }, () => Array.from({ length: col }, () => 0));
const dx = [0, 0, 1, -1];
const dy = [1, -1, 0, 0];
const waterQueue = [];

let sX, sY, eX, eY;
let ans = 0;

for (let i = 0; i < row; i++) {
  for (let j = 0; j < col; j++) {
    if (arr[i][j] === 'S') {
      sX = i;
      sY = j;
    }
    if (arr[i][j] === 'D') {
      eX = i;
      eY = j;
    }
    if (arr[i][j] === '*') {
      waterQueue.push([i, j]);
    }
  }
}

const waterBfs = () => {
  const queue = [];
  for (let [x, y] of waterQueue) {
    for (let i = 0; i < 4; i++) {
      const [nx, ny] = [x + dx[i], y + dy[i]];
      if (nx < 0 || nx >= row || ny < 0 || ny >= col || arr[nx][ny] !== '.') continue;

      arr[nx][ny] = '*';
      queue.push([nx, ny]);
    }
  }
  waterQueue.push(...queue);
};

const bfs = () => {
  let queue = [];
  queue.push([sX, sY, 0]);
  visited[sX][sY] = 1;

  while (queue.length) {
    const qLen = queue.length;
    waterBfs();

    for (let i = 0; i < qLen; i++) {
      const [x, y, cnt] = queue.shift();
      if (x === eX && y === eY) {
        ans = cnt;
        return;
      }

      for (let i = 0; i < 4; i++) {
        const [nx, ny] = [x + dx[i], y + dy[i]];
        if (nx < 0 || nx >= row || ny < 0 || ny >= col || arr[nx][ny] === '*' || arr[nx][ny] === 'X' || visited[nx][ny]) continue;
        visited[nx][ny] = 1;
        queue.push([nx, ny, cnt + 1]);
      }
    }
  }
  return;
};

bfs();

ans > 0 ? console.log(ans) : console.log('KAKTUS');

✔ 알고리즘 : BFS

✔ 입력을 받으면서 시작지점과 끝지점을 sX,sY,eX,eY에 저장하고 물은 waterQueue라는 배열에 넣는다.

✔ 항상 이동 전에 물을 먼저 전파시켜야 한다. wterQueue에 해당하는 좌표만 1차례 전파시키고 waterQueue에 다시 넣는다.

const waterBfs = () => {
  const queue = [];
  for (let [x, y] of waterQueue) {
    for (let i = 0; i < 4; i++) {
      const [nx, ny] = [x + dx[i], y + dy[i]];
      if (nx < 0 || nx >= row || ny < 0 || ny >= col || arr[nx][ny] !== '.') continue;

      arr[nx][ny] = '*';
      queue.push([nx, ny]);
    }
  }
  waterQueue.push(...queue);
};

✔ 물을 전파시켰으면 이제 이동을 해야할 차례이다. 일반적인 bfs함수로 구현하였다.

✔ 시간은 queue에 넣을 때 3번째 인자로 cnt로 측정하였다. 이동할때마다 cnt를 1씩 증가시켜서 queue에 push하였다.

✔ 난이도 : 백준 기준 골드 4