[백준] 1018번 체스판 다시 칠하기 - 파이썬

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

1018번: 체스판 다시 칠하기

문제

풀이

크기가 8 * 8 이상의 체스판이 주어진다. 이 체스판을 8*8크기로 잘라서 체스판으로 만들려고 한다. 잘못된 색이 칠해진 칸은 고쳐준다. 이때 칸의 개수를 최소로 고쳐서 체스판을 만들 수 있는 칸의 개수를 출력하는것이 문제의 목표이다.

 

1, 완전탐색을 통한 8*8크기의 체스판을 추출해야한다.

# 주어진 n과 m에서 7을 빼주어서 추출할 8*8 체스판의 모든 첫번째 칸을 찾아준다.
for y in range(n-7):
    for x in range(m-7):

2, 체스판은 왼쪽 위 첫번째 칸이 검은색으로 시작하거나 하얀색으로 시작하는 경우로 나뉜다.

ex) 하얀색으로 시작하는 체스판으로 잘랐을 경우, 검은색으로 시작하는 체스판으로 잘랐을 경우

이 경우를 나누어서 체스판의 칸을 올바른 색으로 고쳐준다.

만일 <하얀색 검정색 검정색 검정색>의 칸들이 주어진다면 다음과 같이 수정이 가능하다.

 

1, 맨첫번째 칸이 하얀색으로 시작하는 경우

<하얀색 검정색 검정색 검정색>  ->  <하얀색 검정색 하얀색 검정색>

고친 칸의 개수: 2개

 

2, 맨 첫 번째 칸이 검정색으로 시작하는 경우

<하얀색 검정색 검정색 검정색>  ->  <검정색 하얀색 검정색 하얀색>

고친 칸의 개수: 3개

 

이를 변수2개와 if문으로 계산해준다.

# 하얀색 칸으로 시작하는 정사각형이라고 가정했을 때 수정해야할 칸의 개수
        start_white_cnt = 0
        # 검은색 칸으로 시작하는 정사각형이라고 가정했을 때 수정해야할 칸의 개수
        start_black_cnt = 0
        # 추출한 정사각형의 모든 칸을 완전 탐색해준다.
        for i in range(y, y + 8):
            for j in range(x, x+8):
                if (i+j) % 2 == 0:
                    if chess_board[i][j] != "W":
                        start_white_cnt += 1
                    else:
                        start_black_cnt += 1
                else:
                    if chess_board[i][j] != "B":
                        start_white_cnt += 1
                    else:
                        start_black_cnt += 1

전체코드

# 1018번 체스판 다시 칠하기
import sys
n, m = map(int, input().split())
chess_board = [list(sys.stdin.readline().rstrip()) for _ in range(n)]
ans = sys.maxsize
# 체스판의 8*8크기의 정사각형의 시작점을 추출한다.
for y in range(n-7):
    for x in range(m-7):
        # 하얀색 칸으로 시작하는 정사각형이라고 가정했을 때 수정해야할 칸의 개수
        start_white_cnt = 0
        # 검은색 칸으로 시작하는 정사각형이라고 가정했을 때 수정해야할 칸의 개수
        start_black_cnt = 0
        # 추출한 정사각형의 모든 칸을 완전 탐색해준다.
        for i in range(y, y + 8):
            for j in range(x, x+8):
                if (i+j) % 2 == 0:
                    if chess_board[i][j] != "W":
                        start_white_cnt += 1
                    else:
                        start_black_cnt += 1
                else:
                    if chess_board[i][j] != "B":
                        start_white_cnt += 1
                    else:
                        start_black_cnt += 1

        ans = min(ans, start_white_cnt, start_black_cnt)

print(ans)

출력결과