백준 2636 < 치즈 > JavaScript

📍문제 링크

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

2636번: 치즈

 

📍알고리즘 분류

- 구현

- 그래프 이론

- 그래프 탐색

- 너비 우선 탐색

- 시뮬레이션

 

📍문제 풀이

- width, height 정보가 주어지고, 0과 1로 이루어진 2차원 배열의 정보가 주어진다

2차원 배열의 0은 공기, 1은 치즈를 의미한다

2차원 배열의 가장자리는 0이다

 

- 1시간이 지날 때마다 공기중에 노출된 치즈가 녹는다고 할 때, 치즈가 다 녹는데 걸리는 시간과, 마지막 치즈 면적을 구하라

 

백준 2638번 치즈 문제와 비슷한 문제

- 치즈의 면적을 구하지만, 1이 아닌, 0에다 BFS를 실행해야 한다

- 2차원 배열의 가장자리는 0이므로, 0,0 지점에서 BFS를 실행하여 치즈를 녹인다 (공기중에 맞닿은 치즈만 녹이기 위해)

 

치즈를 녹일 배열을 업데이트 하고 BFS가 끝나면 마지막에 치즈를 녹인다

- 중간에 바로 치즈를 녹이면, 그 턴의 정보가 왜곡된다

 

📍코드 (JavaScript)

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const input = [];

rl.on("line", (line) => {
  input.push(line);
}).on("close", () => {
  const [row, col] = input[0].split(" ").map(Number);
  const board = input.slice(1).map((row) => row.split(" ").map(Number));
  const dy = [-1, 1, 0, 0];
  const dx = [0, 0, -1, 1];

  // BFS로 치즈를 녹일 좌표의 배열을 구하는 함수
  const getMeltingPosArr = () => {
    const meltingPosArr = [];
    const queue = [[0, 0]];
    const isVisited = Array.from({ length: row }, (_) =>
      Array.from({ length: col }, (_) => false),
    );
    isVisited[0][0] = true;
    while (queue.length) {
      const [y, x] = queue.shift();
      for (let i = 0; i < 4; i++) {
        const [newY, newX] = [y + dy[i], x + dx[i]];
        if (
          newY >= 0 &&
          newX >= 0 &&
          newY < row &&
          newX < col &&
          !isVisited[newY][newX]
        ) {
          isVisited[newY][newX] = true;
          if (!board[newY][newX]) queue.push([newY, newX]);
          if (board[newY][newX] === 1) meltingPosArr.push([newY, newX]);
        }
      }
    }
    return meltingPosArr;
  };

  // 치즈를 녹일 좌표의 배열 받아서 치즈 녹이는 함수
  const melt = (arr) => {
    arr.forEach((pos) => {
      board[pos[0]][pos[1]] = 0;
    });
  };

  // map의 남은 치즈 면적 계산
  const calcCheeseArea = () => {
    let currentArea = 0;
    board.forEach((row) => {
      currentArea += row.reduce((acc, cur) => acc + cur, 0);
    });
    return currentArea;
  };

  const answer = [0, calcCheeseArea()]; // 좌항에 시간, 우항에 면적
  while (answer[1]) {
    answer[0]++;
    melt(getMeltingPosArr());
    const cheeseArea = calcCheeseArea();
    if (cheeseArea) answer[1] = cheeseArea;
    else break;
  }
  console.log(answer.join("\n"));
});

 

📍리뷰

BFS 대신 DFS를 사용하면 소요 시간이 아주 미세하게 소폭 증가한다

- shift 대신 pop을 사용하여 얻는 시간 보너스는 없다

- 역시 최단 경로를 찾는게 아닌, 완전 탐색의 경우는 BFS가 DFS 보다 빠르다