백준 2638 < 치즈 > JavaScript

📍문제 링크

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

2638번: 치즈

 

📍알고리즘 분류

- 구현
- 그래프 이론
- 그래프 탐색
- 너비 우선 탐색
- 시뮬레이션
- 깊이 우선 탐색

 

📍문제 풀이

1과 0으로 이루어진 n * m 보드가 주어진다.

- 두 면이 0과 접한 1은 1턴 이후에 0으로 변하는데, 모든 1이 0으로 변하는데 몇 턴이 걸리는지 구하라

 

📍1트 : 완전탐색 -> 내부 공간 고려 못해 실패

1. 전체 보드 total 구하기

- total이 0이 아니면 반복

 

2. 중첩 for 문으로 board를 순회

- 1인 좌표에서 상하좌우 스캔

- 상 하 좌 우 스캔하여 0이면 cnt + 1

- cnt >= 2 이면 없앨 좌표로 저장

 

3. 반복문 끝나면 없앨 좌표 모두 0으로 바꿈 (중간 왜곡 방지 위해)

 

그런데.. 내부 공간을 생각 못해서 실패...

1이 아니라 0인 좌표에 dfs를 실행해야 한다..

 

📍2트 : 치즈(1인 원소)가 아닌 공기(0 인 원소)에 dfs 실행

- bfs 대신 dfs를 사용한 이유 (pop이 shift 보다 빠르니까.. 완전 탐색이니까 둘 다 상관없음)

 

1. 0인 원소에 dfs 실행

- 0이면 stack에 넣고

- 1이면 마지막에 위치 바꿀 좌표들의 배열에 넣어 저장

또, 2 이상 접촉 수를 가지기 위해 카운트

 

2. label을 사용하여 중첩 for 문을 한꺼번에 break

📍코드 (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 [N, M] = input.shift().split(" ").map(Number);
  const board = input.map((row) => row.split(" ").map(Number));
  let answer = 0;
  const getAreaVal = (nestedArr) => {
    return nestedArr
      .map((row) => row.reduce((acc, cur) => acc + cur, 0))
      .reduce((acc, cur) => acc + cur, 0);
  };

  // dfs 는 board를 수정하는 역할
  const dfs = (y, x) => {
    const stack = [[y, x]];
    const isVisited = Array.from({ length: N }, (_) =>
      Array.from({ length: M }, (_) => false),
    );
    const adjacentCntArr = Array.from({ length: N }, (_) =>
      Array.from({ length: M }, (_) => 0),
    );
    isVisited[y][x] = true;
    while (stack.length) {
      const [Y, X] = stack.pop();
      // 상하좌우 스캔하여 1이면 인접 카운트 배열에 +1
      // 0이면 미방이면 stack에 넣기
      // 상
      if (Y - 1 >= 0) {
        // 0이면 방문 표시하고 스택에넣기
        if (!board[Y - 1][X] && !isVisited[Y - 1][X]) {
          isVisited[Y - 1][X] = true;
          stack.push([Y - 1, X]);
        }
        // 1이면 인접 카운트 배열에 +1
        if (board[Y - 1][X]) {
          adjacentCntArr[Y - 1][X]++;
        }
      }
      // 하
      if (Y + 1 < N) {
        if (!board[Y + 1][X] && !isVisited[Y + 1][X]) {
          isVisited[Y + 1][X] = true;
          stack.push([Y + 1, X]);
        }
        if (board[Y + 1][X]) {
          adjacentCntArr[Y + 1][X]++;
        }
      }
      // 좌
      if (X - 1 >= 0) {
        if (!board[Y][X - 1] && !isVisited[Y][X - 1]) {
          isVisited[Y][X - 1] = true;
          stack.push([Y, X - 1]);
        }
        if (board[Y][X - 1]) {
          adjacentCntArr[Y][X - 1]++;
        }
      }
      // 우
      if (X + 1 < M) {
        if (!board[Y][X + 1] && !isVisited[Y][X + 1]) {
          isVisited[Y][X + 1] = true;
          stack.push([Y, X + 1]);
        }
        if (board[Y][X + 1]) {
          adjacentCntArr[Y][X + 1]++;
        }
      }
    }
    // 바꿀 좌표들을 찾아내면 0으로 바꿔줌
    for (let i = 1; i < N - 1; i++) {
      for (let j = 1; j < M - 1; j++) {
        if (adjacentCntArr[i][j] >= 2) board[i][j] = 0;
      }
    }
  };

  while (getAreaVal(board) > 0) {
    outer: for (let i = 0; i < N; i++) {
      for (let j = 0; j < M; j++) {
        if (!board[i][j]) {
          dfs(i, j);
          answer++;
          break outer;
        }
      }
    }
  }
  console.log(answer);
});