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

체스판 다시 칠하기

🔍 알고리즘 분류

• 브루트포스

💡 문제 풀이

1. 8*8 크기의 체스판 슬라이싱
   • 시작점 범위는 행(0, n-7), 열(0, m-7)
   • 체스판 범위는 (현재행, 현재행+8), (현재열, 현재열+8)
2. 최소 변경 횟수 구하기
   • 두 패턴 만들기 -> (행+열)==짝수(W) 일때와 (행+열)==홀수(B) 일 때
   • 위 두 패턴별로 짝수/홀수마다 일치하지 않는 칸 개수 카운트
3. 두 패턴별 카운트한 것 중 최솟값을 정답으로 출력

📄 코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
board = [list(input().rstrip()) for _ in range(n)]
answer = int(1e9)

# 두 패턴 중 최소 변환 갯수를 선택
def calculate_min(arr):
    ans1, ans2 = 0, 0
    for i in range(8):
        for j in range(8):
            if (i + j) % 2 == 0: # 짝수
                if arr[i][j] != 'W':
                    ans1 += 1
                else:
                    ans2 += 1
            else: # 홀수
                if arr[i][j] != 'B':
                    ans1 += 1
                else:
                    ans2 += 1
    return min(ans1, ans2)

# 8*8크기의 체스판 슬라이싱
for i in range(n - 7):
    for j in range(m - 7):
        sliced = []
        for x in range(i, i + 8):
            row = ""
            for y in range(j, j + 8):
                row += board[x][y]
            sliced.append(row)
        answer = min(answer, calculate_min(sliced))

print(answer)

• 시간복잡도: O(NM)