BOJ-25682 체스판 다시 칠하기 2 Swift

문제

지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 K×K 크기의 체스판으로 만들려고 한다.

체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.

보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 K×K 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 K×K 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N, M, K가 주어진다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.

출력

첫째 줄에 지민이가 잘라낸 K×K 보드를 체스판으로 만들기 위해 다시 칠해야 하는 정사각형 개수의 최솟값을 출력한다.

내가 푼 풀이

접근방법: 부분합

 

이전에 체스판 다시 색칠하기 1 문제는 브루탈포스로 모든 경우의수를 구해서 대입하고 구했다면,

이 문제는 체스판의 크기가 최대 2000 x 2000 이므로 브루탈포스로는  시간초과가 난다.

부분합을 이용해서 구해보자

주어진 수열에서 i번째까지의 합은 다음과 같다.

 $S_{i} = A(i) + A(i-1) + \cdots + A(1) $

이 성질을 이용해 부분합 i부터 j까지의 합은 다음과 같다.

$S_{ij} = A(j) + A(j-1) + A(j-2) +\cdots + A(i+1) + A(i) = S_{j} - S_{i-1}$

 

이것을 2차원 배열에 적용하는데, 체스판은 총 두가지 경우가 있다.

• 왼쪽상단이 검정색으로 시작하는 경우
• 왼쪽상단이 흰색으로 시작하는 경우

두개의 체스판을 이용하여 2차원배열 부분합을 구한다.

먼저 예시의 체스판과 두개의 정상 체스판을 보자.

Board: 주어진 보드판, Black: 왼쪽 상단이 검정으로 시작, White: 왼쪽 상단이 흰색으로 시작

주어진 보드판을 두개의 정상 체스판처럼 만들어보려고 한다.

 

보드에서 각 칸과 정상 체스판의 색이 같다면 색칠하지 않아도되고, 색이 다르면 색칠을 해줘야 한다.

i행 i열의 값은 1행1열부터 i행 i열까지 색칠한 수를 모두 합한 수가 되도록 구해준다.

이렇게 2차원배열로 부분합을 구해주면 위와 같다.

배열 S[i][j] : 1행1열부터 i행i열까지의 합

 

여기서 주어진 K x K 크기의 체스판을 만들 때 최소로 색칠하는 횟수를 구하려고 한다.

각 배열의 원소는 1행1열부터 색칠한 횟수를 저장했다.

부분합 성질을 이용하여 K크기의 체스판을 만들고, 색칠하는 최솟값을 갱신한다.

 

예시로 중간 2행2열부터 3행3열까지의 부분합을 구해보자.

이를 식으로 나타내면

S[3][3] - S[3][1] - S[1][3] + S[1][1]

 

이렇게 K x K 크기만큼의 부분합을 구해서 최솟값을 구하면 된다.

 

코드로 구현하면 다음과 같다.

import Foundation

// 입력받기
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let N = input[0], M = input[1], K = input[2]

// 체스판의 맨 왼쪽상단이 검정색, 흰색인경우의 두가지 정상 체스판을 미리 만든다.
var black = Array(repeating: Array(repeating: 0, count: M+1), count: N+1)
var white = Array(repeating: Array(repeating: 0, count: M+1), count: N+1)
var first = false
var bl = true
var minSum = Int.max
for i in 1...N {
    if first {
        bl = true
    } else {
        bl = false
    }
    first = !first
    for j in 1...M {
        if bl {
            white[i][j] = 1
        } else {
            black[i][j] = 1
        }
        bl = !bl
    }
}

// 부분합 구하기
for i in 0..<N {
    let arr = Array(readLine()!)
    for j in 0..<arr.count {
        if (black[i+1][j+1] == 0 && arr[j] == "B") || (black[i+1][j+1] == 1 && arr[j] == "W") {
            black[i+1][j+1] = black[i+1][j] + 1 + black[i][j+1] - black[i][j]
        } else {
            black[i+1][j+1] = black[i+1][j] + black[i][j+1] - black[i][j]
        }
        if (white[i+1][j+1] == 0 && arr[j] == "B") || (white[i+1][j+1] == 1 && arr[j] == "W") {
            
            white[i+1][j+1] = white[i+1][j] + 1 + white[i][j+1] - white[i][j]
        } else {
            white[i+1][j+1] = white[i+1][j] + white[i][j+1] - white[i][j]
        }
    }
}

// 해당 부분합중 최솟값 구하기
for i in 1...N-K+1 {
    for j in 1...M-K+1 {
        let whiteSum = white[i+K-1][j+K-1] - white[i+K-1][j-1] - white[i-1][j+K-1] + white[i-1][j-1]
        let blackSum = black[i+K-1][j+K-1] - black[i+K-1][j-1] - black[i-1][j+K-1] + black[i-1][j-1]
        let m = min(whiteSum, blackSum)
        minSum = min(minSum, m)
    }
}
print(minSum)