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

# 문제 링크

www.acmicpc.net/problem/1018

1018번: 체스판 다시 칠하기

# Solution(실패) - 반례를 생각하지 않아서 실패

*반례 -> 8x8 크기로 잡은 판의 첫색의 색이 'W'더라도 'B'인 경우도 같이 확인

n,m = map(int, input().split(' '))
board = []
for _ in range(n):
    board.append(input())
cnt = 8*8
for i in range(n):
    if n-i>=8:
        for j in range(m):
            chk = 0
            if m-j>=8:
                first_color = board[i][j]
                no = 0
                for n1 in range(i,i+8):
                    for n2 in range(j,j+8):
                        if first_color=='W':
                           if no%2==0 and board[n1][n2] != 'W': # W
                                chk+=1
                           elif no%2!=0 and board[n1][n2] != 'B':
                                chk+=1
                        else:
                            if no%2==0 and board[n1][n2] != 'B': # W
                                chk+=1
                            elif no%2!=0 and board[n1][n2] != 'W':
                                chk+=1
                        no+=1
                    no+=1   
                # 최솟값 구하기
                if cnt > chk:
                    cnt = chk
print(cnt)
 

n,m = map(int, input().split(' '))
board = []
for _ in range(n):
    board.append(input())
# 8x8판으로 보기 ,왼쪽위 기준지점 찾기
cnt = 8*8
for i in range(n):
    if n-i>=8:
        for j in range(m):
            chk1 = 0
            chk2 = 0
            if m-j>=8:
                no = 0
                for n1 in range(i,i+8):
                    for n2 in range(j,j+8):
                        if no%2==0:
                            if board[n1][n2] != 'W':
                                chk1+=1
                            if board[n1][n2] != 'B':
                                chk2+=1
                        else:
                            if board[n1][n2] != 'B':
                                chk1+=1
                            if board[n1][n2] != 'W':
                                chk2+=1
                        no+=1
                    no+=1   
                # 최솟값 구하기
                cnt = min(cnt,chk1,chk2)
print(cnt)

6. 최소값이 64개보다는 적을것이므로 임의로 64로 지정 (64보다 더 큰 숫자도 사용가능)

8. 10. 2중 포문을 이용하여 8x8 체스판의 왼쪽위 기준점 잡기

9. 13. 8x8 체스판일 경우 기준점은 i=0, j=0인 지점만 기준점일 수 있다.

   따라서 가로, 세로가 8보다 작아지는 경우에는 배제하기 위해 사용한 if문

10. 왼쪽위 기준점이 'W'일 경우의 최소값을 구하기위한 변수 

11. 왼쪽위 기준점이 'B'일 경우의 최소값을 구하기위한 변수 

13. 기준점을 기준으로 8x8 체스판의 몇번째 칸인지 확인하기위한 변수

     (27. 다음 행으로 넘어가게되면 wb의 순서가 bw로 되므로 +1을 해준다.)

14. 15. 위의 2중 포문은 기준점을 잡기위한 루프문이고, 기준점을 이용하여 구한 8x8 체스판에서 잘못 색칠된 부분을 찾기 한개씩 체크하기위한 for문이다.

16. no의 홀짝을 이용하여 잘못된 색칠된 부분을 체크