[바미] 체스판 다시 칠하기

문제

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

1018번: 체스판 다시 칠하기

코드 및 코드 설명

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

// 보드 상태를 2D 배열로 저장
const board = input.slice(1, N + 1);

function countRepaints(startRow, startCol, board, startColor) {
    let repaintCount = 0;
    const endRow = startRow + 8;
    const endCol = startCol + 8;
    let expectedColor = startColor;

    for (let i = startRow; i < endRow; i++) {
        for (let j = startCol; j < endCol; j++) {
            if (board[i][j] !== expectedColor) repaintCount++;
            expectedColor = expectedColor === 'B' ? 'W' : 'B';
        }
        expectedColor = expectedColor === 'B' ? 'W' : 'B'; // 줄 바뀔 때 색 전환
    }

    return repaintCount;
}

function findMinimumRepaints(board, N, M) {
    let minRepaints = Number.MAX_SAFE_INTEGER;

    for (let i = 0; i <= N - 8; i++) {
        for (let j = 0; j <= M - 8; j++) {
            const repaintsWhiteStart = countRepaints(i, j, board, 'W');
            const repaintsBlackStart = countRepaints(i, j, board, 'B');
            const minRepaintsForCurrentBoard = Math.min(repaintsWhiteStart, repaintsBlackStart);
            minRepaints = Math.min(minRepaints, minRepaintsForCurrentBoard);
        }
    }

    return minRepaints;
}

const result = findMinimumRepaints(board, N, M);
console.log(result);

 

const board = input.slice(1, N + 1);

입력 배열에서 두 번째 요소부터 N+1까지를 슬라이스하여 보드의 행만을 포함하는 배열을 생성해줍니다.

 

function countRepaints(startRow, startCol, board, startColor) {
    let repaintCount = 0;
    const endRow = startRow + 8;
    const endCol = startCol + 8;
    let expectedColor = startColor;

(startRow, startCol)에서 시작하는 8x8 섹션을 체스판 패턴으로 만들기 위해 다시 칠해야 하는 칸의 수를 계산해주는 함수입니다.

시작 색깔(startColor)을 기준으로 예상 색깔을 설정하고, 필요한 변화의 수를 추적할겁니다.

 

    for (let i = startRow; i < endRow; i++) {
        for (let j = startCol; j < endCol; j++) {
            if (board[i][j] !== expectedColor) repaintCount++;
            expectedColor = expectedColor === 'B' ? 'W' : 'B';
        }
        expectedColor = expectedColor === 'B' ? 'W' : 'B'; // 줄 바뀔 때 색 전환
    }
    return repaintCount;
}

8x8 섹션의 각 사각형을 반복하면서 다시 칠해야 할 사각형의 수를 세주는 부분입니다.

중첩된 루프를 통해 각 셀을 확인하고, 셀의 색이 예상 색과 다를 경우 카운트를 증가시켜주며 각 행의 끝에 도달할 때마다 예상 색을 전환합니다.

function findMinimumRepaints(board, N, M) {
    let minRepaints = Number.MAX_SAFE_INTEGER;

보드의 모든 가능한 8x8 섹션에 대해 최소 재도색 횟수를 결정하기 위한 함수입니다.

이 함수를 사용하여 최소 재도색 횟수를 매우 큰 수로 초기화하여, 더 낮은 수치를 찾으면 갱신할 수 있게 하기 위해 생성했습니다.

    for (let i = 0; i <= N - 8; i++) {
        for (let j = 0; j <= M - 8; j++) {
            const repaintsWhiteStart = countRepaints(i, j, board, 'W');
            const repaintsBlackStart = countRepaints(i, j, board, 'B');
            const minRepaintsForCurrentBoard = Math.min(repaintsWhiteStart, repaintsBlackStart);
            minRepaints = Math.min(minRepaints, minRepaintsForCurrentBoard);
        }
    }
    return minRepaints;
}

각 시작점 (i, j)에 대해 흰색 시작과 검은색 시작으로 필요한 재도색 횟수를 계산하고, 두 값 중 최소값을 선택하여 전체 최소값을 갱신해줍니다.

const result = findMinimumRepaints(board, N, M);
console.log(result);

계산된 결과를 출력해줍니다.

문제 풀이

이 문제는 주어진 M*N 크기의 보드에서 8x8 체스판으로 변환할 때 필요한 최소한의 색칠 변경 횟수를 찾는 문제입니다.

체스판은 검은색과 흰색이 번갈아가며 칠해져야 하며, 인접한 칸은 반드시 다른 색이어야 하죠.

 

먼저 주어진 MxN 크기의 보드에서 가능한 모든 8x8 크기의 서브 보드를 슬라이딩 윈도우 기법을 통해 검토해줍니다.

큰 보드의 각 가능한 시작 위치에서 8x8 크기의 윈도우를 생성하여 이동합니다.

M과 N의 최대 크기가 50이므로 최대 43x43개의 다른 8x8 서브 보드를 고려해야 합니다.

이 기법을 통해 각 윈도우(8x8 보드)마다 다시 칠할 필요가 있는 최소 사각형의 수를 계산할 수 있습니다.

 

그 다음 8x8 서브 보드에 대해 두 가지 색칠 패턴을 적용해줍니다.

첫 번째는 맨 왼쪽 상단 칸이 흰색인 경우, 두 번째는 검은색인 경우이기 때문에 이 두 패턴은 체스판의 규칙을 따라 번갈아 가며 색이 칠해져야 합니다.

만약 각 칸을 확인하며 현재의 색상과 목표 색상이 일치하지 않을 경우, 칠해야 할 칸으로 간주하여 횟수를 셉니다.

각 윈도우에 대해 두 패턴 중 더 적은 횟수를 요구하는 패턴을 선택합니다.

 

그 후 모든 가능한 8x8 보드의 위치에서 계산된 최소 변경 횟수를 비교하여, 전체 보드 중에서 가장 적은 수의 칸을 다시 칠해야 하는 경우를 찾습니다. 이는 각 위치에서 계산된 두 패턴의 결과 중 최소값을 전체 최소값과 비교하여 업데이트하는 방식으로 진행됩니다.

슬라이딩 윈도우 기법은 배열이나 리스트의 항목을 순차적으로 탐색할 때 사용하는 알고리즘 기법 중 하나입니다. 이 기법은 "창" 또는 "윈도우"라고 할 수 있는 고정된 크기의 부분 배열이나 서브 리스트를 이동시키면서 문제를 해결합니다. 이 윈도우는 데이터 구조를 통해 한 번에 한 항목씩 앞으로 이동하면서 연속적인 데이터의 범위를 처리합니다.

시간 복잡도

이 문제는 모든 가능한 8x8 서브 보드를 고려해야 하기 때문에 브루트 포스 접근 방식을 사용합니다.

주어진 입력 크기에서 이 방법은 계산 가능한 범위 내에 있어 각 서브 보드 검사는 상수 시간(64칸 검사)에 완료됩니다.

혹여나 최악의 경우에도 43x43x64의 연산만 필요로 하기 때문에 시간 복잡도는 O((N-7) * (M-7) * 64) ≈ O(N * M * 64)이 됩니다.

공간 복잡도

입력으로 주어진 MxN 보드를 저장하기 위해 문자열 형태로 각각의 행을 저장하는 2D 배열을 사용합니다.

M과 N이 최대 50이므로, 이 배열은 최대 50x50의 크기를 가질 수 있고, 각 문자('B' 또는 'W')는 상수 공간을 차지하므로, 전체 배열의 공간 복잡도는 O(N * M)이 됩니다.

 

그리고 함수 내에서 사용되는 변수들은 상대적으로 고정된 수의 추가 공간을 필요로 합니다. 

countRepaints 함수에서는 startRow, startCol, repaintCount, expectedColor 등 몇 개의 변수를 사용되는데 이 변수들은 각 함수 호출 시 임시 공간으로 할당되며, 함수가 종료되면 해제됩니다.

 

findMinimumRepaints 함수에서는 minRepaints, i, j, repaintsWhiteStart, repaintsBlackStart,

minRepaintsForCurrentBoard 등의 변수가 사용됩니다.

이들 변수 역시 각 함수 호출과 함께 임시 공간으로 사용되므로 고정된 상수 공간은 O(1)을 차지하게 됩니다.

 

따라서, 전체 공간 복잡도는 입력 데이터의 크기에 가장 크게 영향을 받고, 추가적으로 사용되는 변수들은 상수 공간을 차지하기 때문에 공간 복잡도에 기여하는 부분이 없기 때문에 O(M*N)이 공간 복잡도가 됩니다.