[백준/python][브루트포스] 백준 1018번 - 체스판 다시 칠하기

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

1018번: 체스판 다시 칠하기

문제

지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다.

체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.

보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8×8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8*8 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.

---

입력

첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.

---

출력

첫째 줄에 지민이가 다시 칠해야 하는 정사각형 개수의 최솟값을 출력한다.

---

제한

8 <= N,M <= 50 (자연수)

---

예제입력 1

8 8
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBBBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW

예제출력 1

1

---

예제입력 2

10 13
BBBBBBBBWBWBW
BBBBBBBBBWBWB
BBBBBBBBWBWBW
BBBBBBBBBWBWB
BBBBBBBBWBWBW
BBBBBBBBBWBWB
BBBBBBBBWBWBW
BBBBBBBBBWBWB
WWWWWWWWWWBWB
WWWWWWWWWWBWB

예제출력 2

12

---

예제입력 3

9 23
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBW

예제출력 3

31

---

코드

from sys import stdin 
r_line = stdin.readline

N, M = map(int, r_line().split()) # M == 너비, N == 높이
arr = [[0]*M for _ in range(N)]

for i in range(N):
    temp = r_line()
    for j in range(M):
        arr[i][j] = temp[j]

x_cnt = M - 8 +1
y_cnt = N - 8 +1
t1 = "W"
t2 = "B"
cnt = 0
min = 64
for i in range(y_cnt):
    for j in range(x_cnt):
        for k in range(2): # 맨위가 w,b 일때 각각 1번씩
            for y in range(i, 8+i):
                for x in range(j, 8+j):
                    if (y+x)%2 == 0 and arr[y][x] == t1:
                        pass
                    elif (y+x)%2 != 0 and arr[y][x] == t2:
                        pass
                    else: # 틀린거임
                        cnt+=1
            t1, t2 = t2, t1
            if min > cnt:
                min = cnt
            cnt = 0
            
print(min)

풀이

(8X8크기)의 체스판을 남는 공간만큼 한 칸씩 수평수직이동하면서 최솟값을 찾아낸다.

체스판의 모양은 2가지밖에 존재하지 않는다.

1. 맨 위쪽 위 칸이 흰색인 경우

2. 맨 위쪽 위 칸이 검은색인 경우  두가지 이다.

 

이때 특징을 알아내서 문제를 풀었는데, 

2가지 경우 중 어떤 경우든 간에, 같은 색깔인 경우 (행과 열)의 index값을 더하면 짝수 또는홀수로 수렴한다.

따라서 더할 때 짝수또는 홀수인지 판별하고, 그것이 맞다면 현재 체스판의 모양과 

같은 모양이므로 넘어간다.

 

else문에서 걸리게 되면 알맞지 않은 모양이기 때문에 cnt값을 +1 증가시킨다.

 

한 번에 검사가 끝났다면,

전 검사보다 최솟값인지 판별하여 대입한다.