[백준] 1018 - 체스판 다시 칠하기

문제

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

지민이는 단위 정사각형으로 나누어져 있는 M X N 크기의 보드를 찾았다. 보드 내 정사각형은 검은색 또는 흰색으로 칠해져 있는데, 지민이는 보드를 잘라서 8 X 8 크기의 체스판을 만들고자 한다.

체스판은 검은색과 흰색이 번갈아가면서 칠해져 있어야 하고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 보드가 체스판처럼 칠해져 있다는 보장이 없어서 지민이는 보드를 잘라낸 후 몇 개의 정사각형을 다시 칠하려고 한다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하여라.

 

 

풀이

좋은 방법이 없을지 좀 오래 고민을 해보았는데, 입력 크기도 작아서 그냥 완전 탐색하는 방식으로 진행했다.

 

1. 체스판 초기화

체스판은 두 가지 형태가 될 수 있다. 흰색으로 시작하는 형태, 검은색으로 시작하는 형태 모두 선언해준다.

size = 8
w_board = ['WB' * (size // 2) if i % 2 == 0 else 'BW' * (size // 2) for i in range(size)]
b_board = ['BW' * (size // 2) if i % 2 == 0 else 'WB' * (size // 2) for i in range(size)]

 

2.입력값 초기화

지민이가 가진 보드의 크기와 보드를 입력받는다.

import sys

N, M = map(int, sys.stdin.readline().split())
board = [sys.stdin.readline().strip() for _ in range(N)]

 

3. 다시 색칠해야 하는 칸의 수를 구하는 함수 생성

자르는 시작 위치에 따라 다시 칠해야 하는 칸의 수를 반복해서 구해야 한다. 보다 기능을 구분하기 쉽게 해당 부분을 함수로 분리했다.

def check_board(board, i, j, mode='W'):
    cnt = 0
    using_board = w_board if mode == 'W' else b_board
    for x in range(size):
        for y in range(size):
            if using_board[x][y] != board[i + x][j + y]:
                cnt += 1
    return cnt

매개변수로는 보드판을 나타내는 board, 자르는 위치를 나타내는 i와 j, 그리고 체스판의 시작 색을 나타내는 mode를 받는다. 구현은 간단하게 반복문으로 값을 비교하는 방식으로 처리했다. 값 비교할 때는 인덱스에 유의해야 한다.

 

4. 결과 출력

흰색으로 시작하는 체스판과 검은색으로 시작하는 체스판 모두 비교하여 그 중 차이가 가장 적은 것을 출력해야 한다.

result = [check_board(board, i, j, mode='W') for i in range(N - size + 1) for j in range(M - size + 1)]
result.extend([check_board(board, i, j, mode='B') for i in range(N - size + 1) for j in range(M - size + 1)])
print(min(result))

 

 

 

참고 문서

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