백준 1018번: 체스판 다시 칠하기

✔ 풀이를 위한 아이디어

• 메모리 초과를 방지하기 위해 input() 대신 sys.stdin.readline() 사용
• 8x8짜리 부분집합이 (N-7)*(M-7)개 나온다는 사실
• 좌표의 합이 짝수인지 홀수인지 살펴보면 체스판처럼 색을 칠할 수 있다는 생각
• 2차원 배열을 x, y 좌표로 다루고 싶다면 chess[y][x]와 같이 활용해야 함
  
  

✔ 코드

import sys

N, M = map(int, sys.stdin.readline().split())

chess = [list(sys.stdin.readline()) for _ in range(N)]
cases = []

for i in range(N-7):
    start_y = i
    for j in range(M-7):
        start_x = j
        count = 0
        # Case1: 짝수면 B, 홀수면 W (BWBWBWBW)
        for y in range(start_y, start_y+8):
            for x in range(start_x, start_x+8):
                if (x+y) % 2 == 0 and chess[y][x] == 'W':
                    count += 1
                elif (x+y) % 2 == 1 and chess[y][x] == 'B':
                    count += 1
        cases.append(count)
        count = 0
        # Case2: 짝수면 W, 홀수면 B (WBWBWBWB)
        for y in range(start_y, start_y+8):
            for x in range(start_x, start_x+8):
                if (x+y) % 2 == 0 and chess[y][x] == 'B':
                    count += 1
                elif (x+y) % 2 == 1 and chess[y][x] == 'W':
                    count += 1
        cases.append(count)

print(min(cases))

✔ 관련 개념

• 브루트 포스 알고리즘: https://hcr3066.tistory.com/26