[백준 알고리즘] 1018번 체스판 다시 칠하기 Python

오늘은 백준에서 1018번문제 체스판 다시 칠하기를 풀어보았다.

 

MN개의 단위 정사각형으로 나뉜 M X N 크기의 보드가 있다.

정사각형들은 검은색 또는 흰색으로 칠해져있고, 이 보드를 잘라 8 X 8 크기의 체스판으로 만들어야 한다.

 

변을 공유하는 두개의 사각형은 다른 색으로 칠해져 있는, 즉 체스판은 검은색가 흰색이 번갈아서 칠해져 있어야 한다.

결국 체스판을 색칠하는 경우는 맨 왼쪽 위칸이 흰색 또는 검은색인 경우 두 가지로 나뉜다.

 

보드는 그런 형식이 지켜져있다는 보장이 없기에 보드를 8 * 8크기의 체스판으로 잘라 몇개의 정사각형을 다시 칠한다.

이 때 다시 칠해야 하는 정사각형의 최소 개수를 구하는 문제이다.

 

N과 M이 첫째 줄에 주어지고 8 <= N,M <= 50 이다. 

둘째줄부터 N개의 줄에는 각 행의 상태가 주어진다. B는 검은색이고 W는 흰색이다.

 

예제 입력은 이렇다.

 

이 문제를 다른 생각 없이 그저 8*8 배열에서 첫 글자(기준색) 기준으로 최소 횟수를 구하다보니 문제를 틀렸다.

틀리고 다시 생각해보니 기준색일 때 뿐만 아니라 다른 색일 경우에도 최소 횟수를 구하고 그 둘을 비교해야 할 것 같았다.

 

import sys
class Board:
    def __init__(self, N, M):
        self.row = N
        self.col = M
        self.board = []

    def inputRow(self, row):
        self.board.append(row)

    def getLowerFix(self):
        min_fix = 50 * 50
        for x in range(0,self.col - 7):
            for y in range(0,self.row - 7):
                    sub_board = self.board[0+y:8+y]
                    fix_cnt = 64
                    for color in ['B','W']:
                        count = 0
                        for idx,row in enumerate(sub_board):
                            sub_row = row[0+x:8+x]
                            if idx % 2 == 0:
                                count += len([col for col in sub_row[0:8:2] if col != color ])
                                count += len([col for col in sub_row[1:8:2] if col == color ])
                            else :
                                count += len([col for col in sub_row[0:8:2] if col == color ])
                                count += len([col for col in sub_row[1:8:2] if col != color ])
                        if fix_cnt > count : fix_cnt = count
                    if min_fix > fix_cnt : min_fix = fix_cnt
                        
        print(min_fix)

def getInput():
    input_list = sys.stdin.readline().strip().split()
    N = int(input_list[0])
    M = int(input_list[1])
    board = Board(N, M)
    [ board.inputRow(sys.stdin.readline().strip()) for cnt in range(0,N) ]
    return board

def main():
    getInput().getLowerFix()

if __name__ == '__main__':
    main()

 

다시 짠다면 보드의 한 줄을 입력 받을 때 마다 줄 당 최소 횟수를 구하는 방법으로 만들고 싶다.