[백준] 25682번: 체스판 다시 칠하기 2 (파이썬/Python)

 

목차

개요

25682번: 체스판 다시 칠하기 2 (acmicpc.net)

25682번: 체스판 다시 칠하기 2

풀이

단계별로 풀어보기에 있는 문제라서 이 문제의 분류가 누적합이라는 것을 아는 상태였으나, 그럼에도 푸는 것이 쉽지 않았다. [BAEKJOON] 25682 체스판 다시 칠하기 2 (tistory.com) 결국 이 분의 글을 참조하여 이해하고 풀어냈다.

무작위로 색칠되어 있는 격자판이 있고, 거기에서 원하는 길이만큼 정사각형 모양으로 잘라내 체스판으로 삼고 싶은 것이다. 이때 무작위로 색칠이 된 판이니 아무리 원하는 곳을 잘라내더라도 추가적으로 색칠해야만 온전한 체크무늬를 가지게 될 수도 있을 것이다. 그러면 최소한으로 색칠을 하는 그 상황일 때는 색칠을 얼마나 하게 될 지를 이 문제는 묻고 있다.

기본 아이디어

이런 모양의 격자판이 있다고 쳐보자. 여기에서 나는 3 * 3의 체스판을 만들어내고 싶다. 딱 보면 알겠지만, 검은색을 포함하게 판을 잘라내야 적게 칠하고(2번) 체스판을 만들 수 있을 것이다.

이를 풀기 위한 기본적인 아이디어는 틀을 만들어서 끼워보며 최소로 색칠해야 하는 구간이 어디 있는지 맞추는 것.
전체 격자판을 통째로 체스판으로 만든다고 치면 위 그림 처럼 두 가지 경우의 체스판을 생각할 수 있을 것이다.
왼쪽 위를 기준으로 검은색이 시작인 체스판과 하얀색이 시작인 체스판.

당연히 전체를 칠할 필요는 없다. 우리는 여기에서 가장 적게 칠할 수 있는 3 * 3의 체스판의 위치만 찾으면 된다. 
하지만 발상하기에는 이런 순서를 따르는 게 더 편리하므로 .

기존의 격자판을 두 가지 경우의 체스판으로 만들 경우 색칠을 해야 하는 경우를 1, 그냥 놔둬도 될 경우 0으로 치고 값을 매겨본다.

우리는 여기에서 1을 가장 적게 포함하는 3 * 3 크기의 판을 잘라내면 되는 것이다!

원래 격자판에서 저 부분을 오려내 좌상단과 중앙만 칠하면 최소한의 색칠 횟수로 체스판을 만들 수 있게 되는 것이다. 

이게 기본 아이디어이고, 이렇게 0,1로 만들어진 행렬에서 1을 최소로 가지는 위치를 찾아낼 때 사용되는 것이 바로 누적합이다.

누적합

누적합은 기본적으로 앞의 있던 값들을 더해가는 방식으로 구성된다.

기존의 리스트에서 인덱스를 올려가면서 값을 누적시켜서 합을 저장하는 것이다. 엄밀하게는 다르지만, 방식 자체는 피보나치랑 비슷하다고 할 수 있다.

이 방식의 장점이 바로 이런 것이다. 내가 원하는 구간합을 구할 수 있게 된다. c부터 e까지의 합을 원한다면 통상적인 방법으로는 c부터 e까지 반복문을 돌아서 합을 구해야할 것이다. 그 다음에 내가 d부터 f까지의 합을 원한다면? 또 반복문을 돌아야 한다.
그렇지만 이렇게 누적합 리스트를 한번만 만들어두면 단 두 원소에만 접근하여 값을 빼주는 것으로 원하는 구간합을 구할 수 있게 되는 것이다. 
미리 데이터를 저장해두는 dp와 결이 비슷하다고도 할 수 있다. 

우리 문제에 대해 생각해보면 3 * 3의 크기를 전체 격자판에 두고 고려해야만 한다. 통상적인 방법이라면 매번 3 * 3 = 9개의 원소를 일일히 더하는 과정을 거쳐야 할 것이다. 그렇지만 누적합을 이용하면 매번 더해주는 과정을 생략하고 빠르게 답을 구할 수 있다는 것!

2차원에서의 누적합은? 이런 식으로 구해준다. 여기에 l 위치에 해당하는 값만 더해주면 l의 누적합을 구하게 되는 것이다.
집합에서 합집합 전체의 크기를 구할 때 일단 두 집합을 더하고 교집합에 해당하는 값을 빼주는 것과 같다. 

구간합을 구하는 방식 역시 비슷하다. 만약 f부터 p(위 예시에서의 답에 해당하는 부분)까지의 구간 합을 구하고 싶다면? 누적합 P - 누적합 M - 누적합 D + 누적합 A가 될 것이다. 9번의 순회를 돌았어야 할 값을 단 4개의 원소를 조회하는 것으로 끝낼 수 있다!

코드

import sys

input = sys.stdin.readline

N, M, K = map(int, input().split())
inlst = [input().rstrip() for _ in range(N)]

B_prefix = [[0 for _ in range(M+1)] for _ in range(N+1)]
W_prefix = [[0 for _ in range(M+1)] for _ in range(N+1)]

for i in range(N):
    for j in range(M):
        if (i + j) % 2:
            if inlst[i][j] == 'B':
                B_prefix[i][j] = 1 + B_prefix[i-1][j] + B_prefix[i][j-1] - B_prefix[i-1][j-1]
                W_prefix[i][j] = 0 + W_prefix[i-1][j] + W_prefix[i][j-1] - W_prefix[i-1][j-1]
            else:
                B_prefix[i][j] = 0 + B_prefix[i-1][j] + B_prefix[i][j-1] - B_prefix[i-1][j-1]
                W_prefix[i][j] = 1 + W_prefix[i-1][j] + W_prefix[i][j-1] - W_prefix[i-1][j-1]
        else:
            if inlst[i][j] == 'B':
                B_prefix[i][j] = 0 + B_prefix[i-1][j] + B_prefix[i][j-1] - B_prefix[i-1][j-1]
                W_prefix[i][j] = 1 + W_prefix[i-1][j] + W_prefix[i][j-1] - W_prefix[i-1][j-1]
            else:
                B_prefix[i][j] = 1 + B_prefix[i-1][j] + B_prefix[i][j-1] - B_prefix[i-1][j-1]
                W_prefix[i][j] = 0 + W_prefix[i-1][j] + W_prefix[i][j-1] - W_prefix[i-1][j-1]

ans = 2000000
for i in range(N - K + 1):
    for j in range(M - K + 1):
        B_sub_sum = B_prefix[i+K-1][j+K-1] - B_prefix[i-1][j+K-1] - B_prefix[i+K-1][j-1] + B_prefix[i-1][j-1]
        W_sub_sum = W_prefix[i+K-1][j+K-1] - W_prefix[i-1][j+K-1] - W_prefix[i+K-1][j-1] + W_prefix[i-1][j-1]
        ans = min(ans, B_sub_sum, W_sub_sum)

print(ans)

이쁘지는 않은 코드. 그러나 분기를 확실하게 나누어 볼 수 있다.

참고로 누적합 리스트를 만들 때는 여분의 공간을 하나 더 만들어놔야 편하게 구간합을 구할 수 있다. 보통 range(1, N+1)라는 식으로 하는 사람들이 많은데 파이썬에서 인덱스에 음수가 들어가면 리스트의 맨 끝쪽의 값을 불러오기 때문에 그냥 range(N)이라고 써도 상관이 없다!

첫 반복문에서 입력값을 순회하면서 B로 시작하는 체스판과 W로 시작하는 체스판을 만드는데 필요한 색칠 횟수 리스트를 만든다. 보다시피 합집합을 구하는 방법을 통해 바로 누적합 리스트로 만들어주는 것을 확인할 수 있다.

이후에는 가능한 모든 구간합을 고려하면서 최소가 되는 값을 찾는 것이다!