2차원 Prefix Sum을 체스판 문제로 이해하기

체스판 다시 칠하기 2

이 문제는 prefix sum을 2차원 배열로 확장하여 해결했어야 하는 문제입니다. 2차원으로 prefix sum 을 확장할 경우 구할 수 있는 합의 구간은 사각형의 넓이와 같이 확장이 됩니다.

이차원으로 확장되었을 경우 prefix[i + 1][j + 1] 의 의미는 어떤 의미를 갖는지가 중요합니다. 이 의미는 (0, 0) 부터 현재 위치 (i, j) 까지의 직사각형 안에 있는 모든 값의 합을 의미합니다.

const prefix = Array.from({ length: R }, () => Array(C).fill(0));

for (let i = 0; i < R; i++) {
  for (let j = 0; j < C; j++) {
    prefix[i + 1][j + 1] = prefix[i + 1][j] + prefix[i][j + 1] - prefix[i][j];
  }
}

위와 같이 정의됩니다. 이 부분은 설명을 들어도 잘 이해가 가지 않으므로 공식이라고 생각하고 기억하는 것이 좋겠습니다.

prefix[i + 1][j + 1] =
  prefix[i + 1][j] + prefix[i][j + 1] - prefix[i][j] + "현재의 값";

$구하려는\_영역 = (위쪽\_영역) + (왼쪽\_영역) - (중복된\_대각선\_영역) + (내\_자리의\_값)$

위의 공식을 기억하고 활용하는 것이 2차원으로 표현되는 prefix sum 문제를 해결하기에 적합한 것 같습니다.

이 문제를 2차원 prefix sum으로 해결했어야 하는 이유는 정답일 경우의 합이 정해져 있었기 때문입니다. 예를 들어 검정색 칸을 0, 흰색 칸을 1이라고 정의하였고 왼쪽 상단의 글자가 "W" 인 경우 크기가 3인 체스 칸의 합은 5로 정해져 있습니다.

그렇기 때문에 현재 칸이 갖는 값과 정답일 경우를 일치하는지 하지 않는지를 기준으로 prefix sum을 작성한다면 정답을 위해서는 몇 번의 작업이 필요한지를 계산할 수 있습니다.

for (let i = 0; i < N; i++) {
  for (let j = 0; j < M; j++) {
    let isMismatch = 0;
    if ((i + j) % 2 === 0) {
      if (board[i][j] !== "B") {
        isMismatch = 1;
      }
    } else {
      if (board[i][j] !== "W") {
        isMismatch = 1;
      }
    }
    psum[i + 1][j + 1] =
      psum[i][j + 1] + psum[i + 1][j] - psum[i][j] + isMismatch;
  }
}

체스의 칸이 홀수인지 짝수인지가 중요하기 때문에 (i + j) % 2를 기준으로 기대 값, 이 경우에는 왼쪽 상단이 검정색인 체스를 가정하고 작업을 하였기 때문에 짝수 칸에 검정색이 아닌 경우에 일치하지 않는 정도를 합산해 가면서 기록할 경우 총 몇 개의 작업이 잘못되었고 정답을 위해서 몇 개의 작업이 필요한지에 대해 계산할 수 있습니다.

성곽

이 문제는 이상적인 해결방법이 비트마스크를 사용하여 해결하는 것이었습니다. 하지만 저는 이 문제를 좌표 확대 문제로 생각하여 해결하고자 했습니다. 좌표 확장 부분에서 어떻게 칸을 옮겨야 하는지에 대해서 고민을 많이 했습니다.

좌표를 확장할 경우에는 원본 크기의 인덱스와 확장한 크기의 인덱스를 구분하여 사용해야 한다는 것을 잊지 말아야 합니다. 좌표를 이동하여 그릴 경우, 벽에 대한 정보를 업데이트를 수행할 경우에는 const r = i * 2; const c = j * 2; 와 같이 확장된 좌표를 기준으로 코드가 작성되어야 합니다. 그리고 기존 원본 코드의 경우는 arr[i][j] 를 통해서 접근하여 새롭게 작성해야 한다는 것을 잊어서는 안 됩니다.

확장 후 원본 영역을 계산해야 하는 경우

또한 확장 후의 기존 영역을 계산하는 부분 또한 신경 써줘야 합니다. 제가 잘못 생각한 부분은 두 배로 확장했으니 이동이 가능한 영역 또한 BFS 탐색을 통해서 얻은 값의 절반 값이 이동이 가능한 영역이라고 생각했다는 점입니다. 하지만 실제로는 다음과 같이 계산해야 합니다.

if (sx % 2 === 0 && sy % 2 === 0) {
  realSize++;
}

이러한 이유는 2배로 확장한 경우에는 벽으로 막히는 부분의 개수가 일정하지 않기 때문에 실제 이동이 가능한 공간의 수를 잘못 계산한다는 문제가 있습니다. 그러므로 현재 좌표가 짝수인 경우에는 2배로 확장하였던 원본 값에 해당하기 때문에 이 값을 비교하는 것이 실제로 이동이 가능한 영역을 계산할 수 있다는 것을 잊지 말아야 합니다.

ID를 기록하여 이동 가능한 영역을 기억하기

그리고 BFS를 통해 막혀 있는 벽을 뚫게 될 경우 한 번의 BFS로 문제를 해결하기 위해서는 id 값을 활용해야 합니다. BFS를 통해서 연결되어 있는 영역들에 대한 계산을 수행한 후 해당 값에 id를 기록하고 벽을 넘어설 경우 서로 다른 id 가 존재하는지를 확인하면 한 번의 BFS를 통해 계산할 수 있기 때문에 이 또한 기억해야 합니다.