백준 알고리즘 - 체스판 다시 칠하기 (Brute Force) [Python]

 

 

 문제

 

www.acmicpc.net/problem/1018

1018번: 체스판 다시 칠하기

 

 

 

 

 

 

 문제 상황

 

- 체스판 색깔이 백, 흑이 반복되어야 하는데 8이상, 50이하 길이의 판이 주어질 때 최소의 색칠로 8 by 8 체스판을 만들 경우의 최소 색칠 수를 반환한다.

 

 

 

 

 

 

 해결 전략

 

- 우선 시작 행, 시작 열을 입력 했을 때 8 by 8 판에 해야 할 색칠의 수를 반환하는 함수를 만들고, 판의 가장 왼쪽 가장 위의 지점을 이동시키며 모든 경우를 탐색한다. 

 

 

 

 

 

 

 코드

 

from sys import stdin, maxsize
 
input = stdin.readline
row, col = map(int, input().split())
chess_board = [[] for _ in range(row)]
for i in range(row):
    chess_board[i] = list(input().strip())
 
 
def check_board(word: str, row: int, col: int, chess_board) -> int:
    cnt = 0
    for i in range(row, row + 8):
        for j in range(col, col + 8):
            if i % 2 == 0:
                if j % 2 == 0 and chess_board[i][j] != word:
                    cnt += 1
                if j % 2 == 1 and chess_board[i][j] == word:
                    cnt += 1
            else:
                if j % 2 == 0 and chess_board[i][j] == word:
                    cnt += 1
                if j % 2 == 1 and chess_board[i][j] != word:
                    cnt += 1
    return cnt
 
 
cnt = maxsize
for i in range(0, row - 7):
    for j in range(0, col - 7):
        cnt = min(cnt, check_board("W", i, j, chess_board))
        cnt = min(cnt, check_board("B", i, j, chess_board))
print(cnt)

 

 

 

 

 

 

 

 

 해설

 

- Brute Force -> 최악의 경우에도 (50-8)*(50-8)을 순회하며 64번 체크하므로 속도에는 문제가 없다.

 

 

 

 

 

 

 

 새로 학습한 것 & 실수 

 

- 네이밍을 row, col로 하여 반복문의 조건도 i, j 가 아니라 row, col로 해서 이상하게 높은 숫자가 나왔다. 항상 조건문, 반복문 등에서 변수명이 중요하다.