[백준] 3055번 탈출 - JavaScript(NodeJS)

문제

3055번: 탈출

 

코드

const sol = (input) => {
  let answer = 0;
  const [R, C] = input[0].split(" ").map(Number);
  const map = input.slice(1).map((str) => str.split(""));
  const check = Array(R)
    .fill()
    .map((_) => Array(C).fill(0));

  let D, S;
  let water = [];
  for (let i = 0; i < R; i++) {
    for (let j = 0; j < C; j++) {
      if (map[i][j] === "D") D = [i, j];
      if (map[i][j] === "S") S = [i, j];
      if (map[i][j] === "*") water.push([i, j]);
    }
  }

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

  function spreadWater() {
    const spread = [];
    for (let [x, y] of water) {
      for (let i = 0; i < 4; i++) {
        const [nx, ny] = [x + dx[i], y + dy[i]];
        if (nx < 0 || ny < 0 || nx >= R || ny >= C) continue;
        if (map[nx][ny] === ".") {
          map[nx][ny] = "*";
          spread.push([nx, ny]);
        }
      }
    }
    water.push(...spread);
  }

  function bfs() {
    const queue = [];
    queue.push([...S, 0]);
    check[S[0]][S[1]] = 1;
    while (queue.length) {
      const len = queue.length;
      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 (nx < 0 || ny < 0 || nx >= R || ny >= C) continue;
          if (map[nx][ny] === "*" || map[nx][ny] === "X" || check[nx][ny]) continue;
          check[nx][ny] = 1;
          queue.push([nx, ny, cnt + 1]);
        }
      }
    }
    return;
  }
  bfs();

  return answer || "KAKTUS";
};

const input = [];
require("readline")
  .createInterface(process.stdin, process.stdout)
  .on("line", (line) => {
    input.push(line);
  })
  .on("close", () => {
    console.log(sol(input));
    process.exit();
  });

 

풀이

티떱 숲의 지도는 R x C 행렬 형태이며 비어있는 곳은 ".", 물이 찬 곳은 "*", 돌은 "X"로 나타낸다.

 

고슴도치 S는 비버의 굴 D로 이동해 홍수를 피하려고 한다.

고슴도치는 매 분마다 현재 칸으로부터 상하좌우에 비어있는 칸으로 이동할 수 있고,
물이 찬 곳도 매 분마다 상하좌우로 퍼져나간다.

 

고슴도치가 비버의 굴 D에 가장 빨리 도착한 시간을 출력하고, 도착할 수 없다면 "KAKTUS" 를 출력한다.

 

풀이 방향

최단경로를 구하는 유형이므로, BFS를 활용한다.

 

고슴도치는 물이 찰 예정인 위치로 이동할 수 없다. 매 분마다 먼저 물을 퍼뜨리고 고슴도치를 이동시킨다.
1분 전에 이동했던 모든 위치에서, 상하좌우의 이동 가능성을 판별해야 다음 1분의 진행이 가능함을 유의한다.
고슴도치가 지나온 경로를 기록하면서 이미 지나온 경로는 다시 돌아가지 않도록 한다.

 

아래는 이해를 돕기 위해 코드에 주석을 달아두었다.

 

주석을 포함한 코드

const sol = (input) => {
  let answer = 0;
  const [R, C] = input[0].split(" ").map(Number); // R,C 값 받기
  const map = input.slice(1).map((str) => str.split("")); // map 행렬 선언
  const check = Array(R).fill().map((_) => Array(C).fill(0));
    // map 크기로 동일한 위치로의 이동을 방지할 배열 선언

  let D, S;
  let water = [];
  for (let i = 0; i < R; i++) {
    for (let j = 0; j < C; j++) {
      if (map[i][j] === "D") D = [i, j];
      if (map[i][j] === "S") S = [i, j];
      if (map[i][j] === "*") water.push([i, j]);
    }
  } // D,S, 물의 좌표를 찾는다.

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

  function spreadWater() {
    const spread = [];
    for (let [x, y] of water) {
      for (let i = 0; i < 4; i++) {
        const [nx, ny] = [x + dx[i], y + dy[i]];
        if (nx < 0 || ny < 0 || nx >= R || ny >= C) continue;
        if (map[nx][ny] === ".") {
          map[nx][ny] = "*";
          spread.push([nx, ny]);
        }
      }
    } // 현재 물들의 위치를 기준으로 상하좌우로 퍼뜨릴 수 있다면 모두 퍼뜨린다.
    water.push(...spread);
    // 퍼진 물의 위치들을 모두 모은 spread 배열의 원소들을 기존의 water 배열에 넣어준다.
  }

  function bfs() {
    const queue = [];
    queue.push([...S, 0]); // S가 고슴도치 위치이므로 여기서부터 시작한다.
    check[S[0]][S[1]] = 1;
    while (queue.length) {
      const len = queue.length; // 현재 queue에 담긴만큼 반복해야 "매 분" 조건이 완성된다.
      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 (nx < 0 || ny < 0 || nx >= R || ny >= C) continue;
          if (map[nx][ny] === "*" || map[nx][ny] === "X" || check[nx][ny]) continue;
          check[nx][ny] = 1;
          queue.push([nx, ny, cnt + 1]);
        } // 상하좌우 이동 가능성을 보고, 이동이 가능하면 고슴도치가 이동한다.
      } // 이 블록까지 수행되어야 1분이 지난 것이다.
    }
    return;
  }
  bfs();

  return answer || "KAKTUS"; // 최단시간이 존재하면 출력하고 존재하지 않는다면(=0) KAKTUS 출력
};

// 백준에서 입력을 받는 코드이다.
const input = [];
require("readline")
  .createInterface(process.stdin, process.stdout)
  .on("line", (line) => {
    input.push(line);
  })
  .on("close", () => {
    console.log(sol(input));
    process.exit();
  });