백준 3055 탈출 (bfs)

문제

제한 사항

입출력 예

풀이

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const sol = (input) => {
  const [row, column] = input.shift().split(" ").map(Number);
  const visited = Array.from(Array(row), () => Array(column).fill(0));
  const table = input.map((e) => e.split(""));

  // 물의 위치들를 저장
  const waterQueue = [];
  // 도착점과 고슴도치 위치를 저장
  let D, S;
  for (let i = 0; i < row; i++) {
    for (let j = 0; j < column; j++) {
      if (table[i][j] === "*") {
        waterQueue.push([i, j]);
      }
      if (table[i][j] === "S") S = [i, j];
      if (table[i][j] === "D") D = [i, j];
    }
  }

  // table을 벗어나면 true를 반환
  const check = (x, y) => {
    if (x < 0 || y < 0 || x >= row || y >= column) {
      return true;
    }
    return false;
  };

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

  const spreadWater = () => {
    const spread = [];
    for (let [x, y] of waterQueue) {
      for (let i = 0; i < 4; i++) {
        const [nx, ny] = [x + dx[i], y + dy[i]];
        if (check(nx, ny)) continue;
        if (table[nx][ny] === ".") {
          table[nx][ny] = "*";
          spread.push([nx, ny]);
        }
      }
    }
    // 퍼지는 위치가 waterQueue에 추가됨
    waterQueue.push(...spread);
  };

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

    while (queue.length) {
      const len = queue.length;
      // for문이 끝날 때 마다 spread해줘야함.
      spreadWater();
      for (let cycle = 0; cycle < len; cycle++) {
        const [x, y, cnt] = queue.shift();
        if (x === D[0] && y === D[1]) {
          answer = cnt;
          return;
        }

        for (let i = 0; i < 4; i++) {
          const [nx, ny] = [x + dx[i], y + dy[i]];
          if (check(nx, ny)) continue;
          // 물이거나 돌이거나 방문한 곳은 못가게
          if (table[nx][ny] === "*" || table[nx][ny] === "X" || visited[nx][ny])
            continue;

          visited[nx][ny] = 1;
          queue.push([nx, ny, cnt + 1]);
        }
      }
    }
    // while까지 다 돌고 나서 return임.
    return;
  };

  bfs();
  return answer ? answer : "KAKTUS";
};

console.log(sol(input));

복잡하긴 하나 기본 bfs와 비슷하다.

물이 고여있는 위치를 따로 배열을 만들어 넣어둔다. 물이 퍼지는 함수를 만든다. 원리는 bfs와 비슷하지만 조금 다르다. 물이 퍼질 수 없는 좌표는 걸러주고 물로 바꾼다. 그리고 그 위치를 배열에 추가시킨다.

bfs 함수에 다른 점이 있다. while문의 한 사이클마다 for문을 새로 돌아 주는 것이다. 이것의 이유는 spread 함수를 사용해야하는 타이밍이 고슴도치의 이동 전에 있어야 하기 떄문이다. 이 점을 유의해서 코드를 잘 파악하자.