[백준] 25682번 : 체스판 다시 칠하기 2 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

http://https://www.acmicpc.net/problem/2568

 

1. 문제 설명

반응형

2. 풀이과정

해당 문제가 누적합 문제로 분류되어 있길래 어떻게 누적합으로 해결할 수 있을지 고민을 해보았지만 쉽게 해결방법이 떠오르지 않았다.

이전 체스판 다시 칠하기 문제를 기억해 보면 기본적으로 체스판은 제일 위쪽 첫 번째 칸이 검은색인지, 흰색인지에 따라 2가지 경우를 고려해야 한다는 것을 알 수 있다.

그리고 각 체스판의 칸에 대해 살펴보면 행 인덱스와 열 인덱스의 합이 짝수이면 시작 칸의 색과 동일해야 하고, 홀수이면 시작 칸의 색과 다른 색이어야 한다.

이를 통해 각 2가지 체스판과 주어진 보드를 비교하여 색을 다시 칠해야 하는 부분과 칠하지 않아도 되는 부분을 구별한다. (구별은 칠해야 하면 1, 칠하지 않아도 되면 0으로 구분)

전체 보드 크기에서 주어진 크기의 체스판을 찍어가며 새로 칠해야 하는 칸의 개수를 구하고 전체 경우 중 최솟값을 구하면 되는 문제이다.

여기서 2차원 리스트에 누적합이 사용된다.

체스판을 찍어가며 새로 칠해야 하는 칸의 개수를 매번 구하는 것은 많은 시간이 소요된다.

하여 새로 칠해야 하는 칸의 개수를 누적합으로 2차원 리스트에 저장해 두고 이를 활용하여 각 체스판의 경우마다 새로 칠해야 하는 칸의 개수를 쉽게 구한다.

2차원 리스트에서 누적합은 df[3][2] = df[3][1] + df[2][2] - df[2][1] 이고, 이를 수식으로 나타내면

df[row][col] = df[row][col - 1] + df[row - 1][col] - df[row - 1][col - 1] 으로 나타낼 수 있다.

2차원 리스트의 누적합을 사용하여 각 체스판의 마지막 칸의 누적합 값이 해당 체스판의 새로 칠해야 하는 칸의 수가 된다.

 

1. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys
2. 각 보드의 가로, 새로, 체스판의 크기를 입력받는다. N, M, K = map(int, sys.stdin.readline().split())
3. 보드의 정보를 한 줄씩 입력받아 개별 문자로 분리해 2차원 리스트로 저장한다. board = list(list(sys.stdin.readline().rstrip()) for _ in range(N))
4. 체스판의 시작 칸의 색에 따라 새로 칠해야 하는 칸의 최솟값을 구하는 함수를 정의한다. def check(start_color)
   1. 새로 칠해야 하는 칸 개수의 누적합을 저장할 2차원 리스트를 생성한다. dp = [[0] * (M + 1) for _ in range(N + 1)]
   2. 각 행별 열 별로 위치를 하나씩 불러와 for row in range(N): for col in range(M)
      1. 만약 행과 열의 인덱스 값의 합이 짝수이면 시작 칸의 색과 다른지 비교하여 그 결과를 변수에 저장한다. if ((row + col) % 2 == 0): v = (board[row][col] != start_color)
      2. 반면에 행과 열의 인덱스 값의 합이 홀수이면 시작 칸의 색과 같은지 비교하여 그 결과를 변수에 저장한다. else: v = (board[row][col] == start_color)
      3. 인덱스는 0부터 시작하므로 누적합을 [1, 1] 위치부터 저장한다.(-1 인덱스 주의!) 위에서 설명한 2차원 리스트의 누적합 수식에 따라 각 칸에 누적합 결과를 저장한다. dp[row + 1][col + 1] = dp[row][col + 1] + dp[row + 1][col] - dp[row][col] + v
   3. 새로 칠해야 하는 칸의 최솟값을 저장할 변수를 생성하고, 새로 칠해야 하는 칸의 최대 개수로 저장한다. MIN = N * M
   4. 가능한 각 체스판을 찍어내며 for row in range(1, N - K + 2): for col in range(1, M - K + 2)
      1. 이전의 최솟값과 현재 찍어낸 체스판에서 새로 칠해야 하는 칸의 개수 중 최솟값을 새로 저장한다. MIN = min(MIN, dp[row + K - 1][col + K - 1] - dp[row + K - 1][col - 1] - dp[row - 1][col + K - 1] + dp[row - 1][col - 1])
   5. 최종 최솟값의 결과를 반환한다. return MIN
5. 시작 칸의 색이 검은색인 체스판의 경우와 흰색인 체스판의 경우 각각 새로 칠해야 하는 칸의 최솟값을 구하고 그 두 가지 경우 중 최종 최솟값을 정답에 저장한다. answer = min(check('B'), check('W'))
6. 최종 정답을 출력한다. print(answer)

3. 소스코드

import sys

N, M, K = map(int, sys.stdin.readline().split())

board = list(list(sys.stdin.readline().rstrip()) for _ in range(N))

def check(start_color):
    dp = [[0] * (M + 1) for _ in range(N + 1)]
    for row in range(N):
        for col in range(M):
            if ((row + col) % 2 == 0):
                v = (board[row][col] != start_color)
            else:
                v = (board[row][col] == start_color)

            dp[row + 1][col + 1] = dp[row][col + 1] + dp[row + 1][col] - dp[row][col] + v

    MIN = N * M
    for row in range(1, N - K + 2):
        for col in range(1, M - K + 2):
            MIN = min(MIN, dp[row + K - 1][col + K - 1] - dp[row + K - 1][col - 1] - dp[row - 1][col + K - 1] + dp[row - 1][col - 1])

    return MIN

answer = min(check('B'), check('W'))
print(answer)