[BOJ] 1018번: 체스판 다시 칠하기

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

1018번: 체스판 다시 칠하기

 

Python3

def coloring(color, str_h, str_w):
    cnt = 0
    for h in range(str_h, str_h+8):
        for w in range(str_w, str_w+8):
            if h % 2 == 0:
                if w % 2 == 0:
                    if color != board[h][w]:
                        cnt += 1
                else:
                    if color == board[h][w]:
                        cnt += 1
            else:
                if w % 2 == 0:
                    if color == board[h][w]:
                        cnt += 1
                else:
                    if color != board[h][w]:
                        cnt += 1
    return cnt


def divide(color):
    min_num = N*M
    for str_h in range(0, N-8+1):
        for str_w in range(0, M-8+1):
            min_num = min(min_num, coloring(color, str_h, str_w))
    return min_num


if __name__ == '__main__':
    N, M = map(int, input().split())

    board = []
    for i in range(N):
        board.append(list(str(input())))

    print(min(divide('B'), divide('W')))

전체 코드는 다음과 같다. 함수로 코드를 작성하는게 좀 더 이해하기 쉬워서 함수를 많이 사용했다.

전체 코드 흐름을 보자면 main함수에서는 입력을 받고 B로 칠하기 시작할 경우와 W로 칠하기 시작할 경우로 나누어 최소로 다시 칠하는 횟수를 비교했다. divide함수는 입력으로 받은 N*M짜리의 판을 8*8 사이즈로 나누는 함수이고 coloring 함수는 8*8짜리의 체스판에서 몇 개의 칸을 다시 칠해야하는지 구하는 함수이다.

 

• main

if __name__ == '__main__':
    N, M = map(int, input().split())

    board = []
    for i in range(N):
        board.append(list(str(input())))

    print(min(divide('B'), divide('W')))

N, M사이즈를 입력받고 체스 보드를 입력받는다. 이때 공백없이 주어지는 문자열의 경우 문자열로 input을 받고 list를 씌워주면 한글자씩 나뉘어 리스트로 저장된다. 즉 board 는 N*M크기의 배열이 된다.

이후 B로 시작했을 경우와 W로 시작했을 경우 각각 다시 칠하는 횟수를 구해 그중 최소값을 출력한다.

 

• divide

def divide(color):
    min_num = N*M
    for str_h in range(0, N-8+1):
        for str_w in range(0, M-8+1):
            min_num = min(min_num, coloring(color, str_h, str_w))
    return min_num

N, M 사이즈에서 8*8로 자를 수 있는 각 가지수를 구하기 위해서는 N-8, M-8을 통해 가로, 세로를 각각 몇칸 움직여서 나눌 수 있나를 구할 수 있다. 이를 바탕으로 8*8 체스판의 시작 위치를 지정하여 이를 가지고 coloring 함수를 호출하였다. coloring함수는 주어진 체스판의 다시 칠하기 횟수를 반환하므로 여러개의 자르는 방식 중에 최소값을 구하기 위해서 min_num 변수를 사용했다.

 

 

• coloring

def coloring(color, str_h, str_w):
    cnt = 0
    for h in range(str_h, str_h+8):
        for w in range(str_w, str_w+8):
            if h % 2 == 0:
                if w % 2 == 0:
                    if color != board[h][w]:
                        cnt += 1
                else:
                    if color == board[h][w]:
                        cnt += 1
            else:
                if w % 2 == 0:
                    if color == board[h][w]:
                        cnt += 1
                else:
                    if color != board[h][w]:
                        cnt += 1
    return cnt

시작하는 color와 시작 위치를 인자로 받아 다시 칠할 횟수를 센다.  홀수 행의 홀수 열의 경우 시작 color와 같고 홀수 행의 짝수 열의 경우 시작 color와 달라야한다. 짝수 행의 홀수 열의 경우 시작 color와 달라야하고 짝수행의 짝수 열의 경우 시작 color와 같아야한다. 이 경우에 대해 맞지 않을 경우 색을 다시 칠해야하므로 해당 카운트를 cnt에 증가시켰다.