[백준 알고리즘: python 3] #1018 - 체스판 다시 칠하기

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

 

1018번 문제는 체스판 다시 칠하기 문제입니다. 엄청 어렵지는 않지만, 차근차근 코드를 짜는 것이 중요한 문제라고 생각합니다.

 

문제를 간단히 설명하자면, 지민이가 흰색이나 검정색으로 색칠되어 있는 단위 정사각형으로 이루어진 N * M 크기의 보드를 찾았고, 이 보드를 8 * 8 크기로 잘랐을 때 체스판이 되기 위해 추가적으로 칠해야할 부분의 최소 개수를 구하는 문제입니다. 체스판의 정의는 우리가 잘 알고 있는 체스판처럼 흰색과 검정색으로 번갈아져 색칠되어 있으면 되어져 있는 보드를 의미합니다.

 

이 때, 체스판은 제일 왼쪽 상단 정사각형의 색이 흰색 혹은 검정색으로 칠해져 있는 총 두가지의 종류로 이루어질 수 있습니다. 저는 이 점을 힌트로 삼아 문제를 풀이하였습니다. 왼쪽 상단이 검정색일 경우와 흰색일 경우를 나누어 생각하였습니다.

 

Hint!

저는 간단히 말하면 전수조사를 했습니다. 입력으로 주어지는 지민이가 발견한 보드는 최대 50 * 50 크기이고, 이 경우에 8 * 8 크기의 체스판을 자르는 모든 경우를 고려한다고 해도 43 * 43 가지 경우의 수밖에 없기 때문입니다. 지금까지 문제를 풀어봤을 때, 이 정도 전수 조사는 충분히 진행될 수 있습니다. 8 * 8 크기로 자른 모든 체스판 경우의 수 중, 지민이가 다시 칠해야 할 부분이 가장 적은 체스판을 찾는 것입니다.

 

따라서, 입력으로 주어진 보드의 왼쪽 제일 상단에 있는 색이 흰색이냐, 검은색이냐에 따라 그 보드가 정상적인 체스판이 되기 위해 페인트를 칠해야 하는지 말아야 하는지 알려주는 리스트를 만들었습니다. 문제에서 주어진 예시를 들어 설명하자면,

 

WBWBWBWB

BWBWBWBW

WBWBWBWB

BWBBBWBW

WBWBWBWB

BWBWBWBW

WBWBWBWB

BWBWBWBW

 

이러한 체스판이 있을 때, 왼쪽 제일 상단에 있는 색이 흰색인 체스판의 경우 색칠해야하는 영역은

 

00000000

00000000

00000000

00010000

00000000

00000000

00000000

00000000

 

이렇게 4번째 줄, 4번째 열만 흰색으로 색칠해야함을 알려주는 리스트를 만들겠다는 뜻입니다. 반대로, 왼쪽 제일 상단에 있는 색이 검은색인 체스판의 경우 색칠해야하는 영역은

 

11111111

11111111

11111111

11101111

11111111

11111111

11111111

11111111

 

이 되겠지요. 이 두 경우의 리스트를 만든 뒤, 각각의 리스트에 대해서, 8 * 8의 판을 가능한 모든 경우로 잘라 1의 개수를 세었을 때, 그 값이 최소인 것을 구하는 것이 제 아이디어의 핵심이었습니다. 약간 무식한 방법이기도 했죠... 코드로 구현할 때는 리스트의 인덱스에 주의하면서 짜야합니다.

 

이 아이디어로 한 번에 성공하였고, 코드는 아래와 같습니다.

import sys

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

board = []
white_first = []
black_first = []

for _ in range(N):
    row = sys.stdin.readline().replace("\n", "")
    board.append([i for i in row])

initial_color = board[0][0]

# 흰색으로 시작하는 체스판을 만들 경우
for index, row in enumerate(board):
    painting = []
    if index % 2 == 0: current_color = "W"
    else: current_color = "B"

    for value in row:
        if value == current_color: painting.append(0)
        else: painting.append(1)
        
        if current_color == "W": current_color = "B"
        else: current_color = "W"
    white_first.append(painting)

# 검은색으로 시작하는 체스판을 만들 경우
for index, row in enumerate(board):
    painting = []
    if index % 2 == 0: current_color = "B"
    else: current_color = "W"

    for value in row:
        if value == current_color: painting.append(0)
        else: painting.append(1)
        
        if current_color == "W": current_color = "B"
        else: current_color = "W"
    black_first.append(painting)

# 최솟값을 초기화 할 때, 보드의 최대 크기인 50*50 = 2500으로 한다.
min_count = 2500
for i in range(N-8+1):
    rows = white_first[i:i+8]
    for j in range(M-8+1):
        paint = 0
        for row in rows:
            paint += sum(row[j:j+8])
        if paint < min_count: min_count = paint

for i in range(N-8+1):
    rows = black_first[i:i+8]
    for j in range(M-8+1):
        paint = 0
        for row in rows:
            paint += sum(row[j:j+8])
        if paint < min_count: min_count = paint

print(min_count)