[알고리즘/백준/16946] 벽 부수고 이동하기 4 (node.js) - 매번 나머지 연산 시 실패한다면?

문제

---

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

 

풀이

---

• 모든 1에서 BFS를 돌면 (NM)^2으로 시간초과
• 벽 주변의 0 묶음의 개수를 더하면 이동할 수 있는 영역이다.
• 따라서 이동 가능한 영역인 0 묶음의 개수를 세어 주변 벽인 1에 더해준다.
• 모듈러 연산의 분배법칙을 생각하고 매번 나눠주는 경우, board 원본 배열의 벽을 증가시키다 10의 배수가 되는 경우 0이 되어 벽으로 인식하지 못하는 문제가 생기므로 유의해야 한다. 
• 시간복잡도: O(NM)

class Queue {
  constructor() {
    this.data = [];
    this.head = 0;
    this.tail = 0;
  }
  push(item) {
    this.data[this.tail++] = item;
  }
  pop() {
    this.head++;
  }
  front() {
    return this.data[this.head];
  }
  rear() {
    return this.data[this.tail - 1];
  }
  isEmpty() {
    return this.head === this.tail;
  }
  size() {
    return Math.abs(this.head - this.tail);
  }
}

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let [n, ...input] = fs.readFileSync(filePath).toString().trim().split("\n");
const [N, M] = n.split(" ").map(Number);
const board = input.map((row) => row.split("").map(Number));

const visited = Array.from({ length: N }, () => Array(M).fill(false));
const dir = [
  [-1, 0],
  [1, 0],
  [0, -1],
  [0, 1],
];

function isOutside(x, y) {
  return x < 0 || y < 0 || x >= N || y >= M;
}

// 0 묶음 찾고, 주변 1들에 0 개수 더해주기
function BFS(sx, sy) {
  const queue = new Queue();
  const walls = []; // 주변 1 담을 변수
  let count = 1;
  queue.push([sx, sy]);
  visited[sx][sy] = true;

  while (!queue.isEmpty()) {
    const [x, y] = queue.front();
    queue.pop();

    for (let k = 0; k < 4; k++) {
      const nx = x + dir[k][0];
      const ny = y + dir[k][1];

      if (isOutside(nx, ny) || visited[nx][ny]) continue;

	  // 0인 경우 현재 묶음에 개수 더해주고 
      if (board[nx][ny] === 0) {
        visited[nx][ny] = true;
        queue.push([nx, ny]);
        count += 1;
      } else {
        // 벽(1 이상)이면 walls에 넣기 
        walls.push([nx, ny]);
        visited[nx][ny] = true;
      }
    }
  }

  // 주변 벽에 0묶음 개수 더해주기 
  for (let [x, y] of walls) {
    board[x][y] += count;
    visited[x][y] = false;
  }
}

// 0 묶음 찾기
for (let i = 0; i < N; i++) {
  for (let j = 0; j < M; j++) {
    if (!visited[i][j] && board[i][j] === 0) {
      BFS(i, j);
    }
  }
}

console.log(board.map((row) => row.map((x) => x % 10).join("")).join("\n"));

너무 너무 괴로웠던 문제..

문제 자체가 아니라 원본 배열 변경 시의 side effect를 고려하지 못한 것이 문제였다. 질문 게시판을 보니 나 같은 사람들이 꽤 있었다.

헷갈릴만한 부분이라 관련 내용을 정리하고 넘어가야겠다. 

 

나머지 연산은 덧셈, 뺄셈, 곱셈에 대해 분배 법칙이 성립한다.

(A + B) mod C = (A mod C + B mod C) mod C
(A - B) mod C = (A mod C - B mod C) mod C
(A * B) mod C = (A mod C * B mod C) mod C

예를 들어, (5 + 11) mod 7 = (5 mod 7 + 11 mod 7) mod 7 = 2가 된다.

 

코테에서 일반적인 범위를 벗어나는 경우 나머지 연산을 활용하라고 할 때가 있다. (보통 DP에서)

경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요.

for(let i=2;i<=n;i++)
	for (let j = 0; j <= 9; j++) 
		for (let k = 0; k <= j; k++) { 
			d[i][j] += d[i - 1][j-k];
			d[i][j] %= mod; // 이런 식으로 누적한 값에 계속 나눠준다.
}

for (let i = 0; i <= 9; i++) {
	ans += d[n][i];
}
	

ans %= mod;

위의 내용처럼,

 

각 dp 테이블의 값을 더해줄 때마다 모듈러 연산을 해준 다음, 최종 ans 값에 모듈러 연산을 하는 것은

(A mod C + B mod C) mod C

 

최종 ans 값에 모듈러 연산을 하는 것과 같다.

(A + B) mod C

 

 

그렇다면 이번 문제에서 내가 실수한 모듈러 연산은?

function BFS(sx, sy) {
  const queue = new Queue();
  const walls = [];
  let count = 1;
  queue.push([sx, sy]);
  visited[sx][sy] = true;

  while (!queue.isEmpty()) {
    const [x, y] = queue.front();
    queue.pop();

    for (let k = 0; k < 4; k++) {
      const nx = x + dir[k][0];
      const ny = y + dir[k][1];

      if (isOutside(nx, ny)) continue;

      if (!visited[nx][ny] && board[nx][ny] === 0) {
        visited[nx][ny] = true;
        queue.push([nx, ny]);
        count += 1;
      } else if (!visited[nx][ny] && board[nx][ny] !== 0) {
        walls.push([nx, ny]);
        visited[nx][ny] = true;
      }
    }
  }

  for (let i = 0; i < walls.length; i++) {
    const [x, y] = walls[i];
    board[x][y] += count;
    // board[x][y] = (board[x][y] + count) % 10
    visited[x][y] = false;
  }
}

BFS 내에서 board[x][y]을 각각 더해주면서 모듈러 연산을 했을 때 답이 틀렸다고 나왔다. 모듈러 연산 분배 법칙을 적용하려면 더해줄 때, 그리고 최종 값에 %10을 해주면 된다고 생각했는데 틀렸다. 왜 그런거지?

console.log(board.map((row) => row.map((x) => x % 10).join("")).join("\\n"));

이건 board[x][y]를 변경했을 때 10이 되는 순간 값이 0이 되고, 더 이상 벽인 1으로 인식하지 않기 때문이다. 해결책은 두 가지이다.

• 원본 배열을 바탕으로 벽을 파악하고 복사본에 값을 업데이트하거나
• 원본 배열을 변경하는 경우에는 모두 판을 완성한 다음에 %10을 해줘야 한다.