[Javascript][백준] 체스판 다시 칠하기 2

 

문제

기존 문제인 체스판 다시 칠하기의 경우에는 제한 사항이 여유로워서 단순히 브루트포스로 해결이 가능하지만, 해당 문제의 경우 문제의 제한 사항(N, M ≤ 2000, 1 ≤ K ≤ min(N, M))과 시간 제한 1초를 고려했을 때, O(N²) 이하의 시간복잡도를 가진 알고리즘을 설계해야 합니다.

 

영역을 선택할 때, 중복되는 영역을 선택하는 경우가 발생하기 때문에 모든 영역마다 K²개의 칸을 다시 계산하는 것은 비효율적입니다. 이 중복 계산을 피하기 위해서 누적합을 사용할 수 있습니다.

 

이 문제를 해결하기 위해 다음과 같은 단계를 거칩니다:

1. 각 칸이 두 가지 체스판 패턴(흰색/검은색 시작)과 얼마나 다른지 계산
2. 이 정보를 바탕으로 누적합 계산
3. 모든 가능한 K×K 영역에 대해 최소 변경 수 계산

 

풀이

• 시간복잡도: O(N×M) (N: 보드의 세로 길이, M: 보드의 가로 길이)

const input = require('fs').readFileSync("/dev/stdin").toString().trim().split('\n');
const [N, M, K] = input[0].split(" ").map(Number);
const board = input.slice(1, N + 1);

function solution() {
    // 보드 전체에 대해 다시 칠해야 하는지 여부를 계산
    // 1: 다시 칠해야 함, 0: 그대로 두면 됨
    const whiteStart = Array.from({ length: N }, () => Array(M).fill(0));
    const blackStart = Array.from({ length: N }, () => Array(M).fill(0));

    // 모든 칸에 대해 두 가지 경우(흰색/검은색 시작) 모두 계산
    for (let i = 0; i < N; i++) {
        for (let j = 0; j < M; j++) {
            // 흰색으로 시작하는 체스판일 때 예상 색상
            const expectedWhiteStart = ((i + j) % 2 === 0) ? 'W' : 'B';

            if (board[i][j] !== expectedWhiteStart) {
                whiteStart[i][j] = 1;
            } else {
                blackStart[i][j] = 1;
            }
        }
    }

    // 누적합 계산 (흰색 시작)
    const prefixWhite = Array.from({ length: N + 1 }, () => Array(M + 1).fill(0));
    for (let i = 0; i < N; i++) {
        for (let j = 0; j < M; j++) {
            prefixWhite[i + 1][j + 1] = prefixWhite[i + 1][j] + prefixWhite[i][j + 1] - prefixWhite[i][j] + whiteStart[i][j];
        }
    }

    // 누적합 계산 (검은색 시작)
    const prefixBlack = Array.from({ length: N + 1 }, () => Array(M + 1).fill(0));
    for (let i = 0; i < N; i++) {
        for (let j = 0; j < M; j++) {
            prefixBlack[i + 1][j + 1] = prefixBlack[i + 1][j] + prefixBlack[i][j + 1] - prefixBlack[i][j] + blackStart[i][j];
        }
    }

    // 모든 가능한 KxK 체스판 위치에서 최소값 찾기
    let minRepaints = Infinity;

    for (let i = K; i <= N; i++) {
        for (let j = K; j <= M; j++) {
            // KxK 영역의 다시 칠해야 하는 칸의 수 계산 (흰색 시작)
            const whiteCaseRepaints = prefixWhite[i][j] - prefixWhite[i - K][j] - prefixWhite[i][j - K] + prefixWhite[i - K][j - K];

            // KxK 영역의 다시 칠해야 하는 칸의 수 계산 (검은색 시작)
            const blackCaseRepaints = prefixBlack[i][j] - prefixBlack[i - K][j] - prefixBlack[i][j - K] + prefixBlack[i - K][j - K];

            // 더 작은 값을 선택
            minRepaints = Math.min(minRepaints, whiteCaseRepaints, blackCaseRepaints);
        }
    }

    return minRepaints;
}

console.log(solution());

누적합을 이용한 K×K 영역 계산은 아래와 같이 이루어집니다.

누적합 영역 계산 방법

여기서 약간 헷갈릴 수 있는 부분은 "전체 보드의 체스판 패턴"과 "선택된 K×K 영역의 체스판 패턴" 사이의 관계입니다. 코드에서 다음 부분을 살펴보겠습니다:

const whiteRepaints = prefixWhite[i][j] - prefixWhite[i - K][j] - prefixWhite[i][j - K] + prefixWhite[i - K][j - K]; 
const blackRepaints = prefixBlack[i][j] - prefixBlack[i - K][j] - prefixBlack[i][j - K] + prefixBlack[i - K][j - K];

whiteRepaints는 "전체 보드가 (0,0)에서 흰색으로 시작하는 체스판이라면, 현재 선택한 K×K 영역을 이 패턴에 맞추기 위해 다시 칠해야 하는 칸의 수"를 계산합니다. blackRepaints도 유사하게 "전체 보드가 (0,0)에서 검은색으로 시작하는 체스판"에 맞추는 비용을 계산합니다.

 

그런데 우리가 실제로 원하는 것은 "K×K 영역 자체를 왼쪽 위가 흰색 또는 검은색인 체스판으로 만드는 비용"입니다. 얼핏 보면 다른 개념처럼 보이지만, 이 두 계산은 같은 결과를 도출합니다.

왜 이 방법이 작동하는가?

K×K 영역을 "왼쪽 위가 흰색인 체스판"으로 만드는 비용은 다음 중 하나와 동일합니다:

• 이 영역이 전체 패턴(흰색 시작)과 일치하도록 만드는 비용
• 이 영역이 전체 패턴(검은색 시작)과 일치하도록 만드는 비용

어떤 것을 사용해야 하는지는 K×K 영역의 왼쪽 위 칸 (i-K,j-K)의 위치에 따라 달라집니다:

• 만약 (i-K,j-K) 위치가 전체 흰색 시작 패턴에서 흰색이어야 한다면, whiteRepaints가 해당 영역을 왼쪽 위가 흰색인 체스판으로 만드는 비용입니다.
• 만약 (i-K, j-K) 위치가 전체 흰색 시작 패턴에서 검은색이어야 한다면, blackRepaints가 해당 영역을 왼쪽 위가 흰색인 체스판으로 만드는 비용입니다.

결국 항상 min(whiteRepaints, blackRepaints)를 선택함으로써, 각 K×K 영역에 대해 "왼쪽 위가 흰색인 체스판"과 "왼쪽 위가 검은색인 체스판" 중 더 적은 변경이 필요한 패턴을 선택합니다.