백준 1018 - 체스판 채우기[부르트포스]

 

 

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

1018번: 체스판 다시 칠하기

 

 

나의 코드

n,m=map(int,input().split())

arr=[list(map(str,input())) for _ in range(n)]
arr1=[[0]*m for _ in range(n)]
ch=[[0]*m for _ in range(n)]
ch1=[[0]*m for _ in range(n)]

for i in range(n):
    for j in range(m):
        arr1[i][j]=arr[i][j]

arr[0][0]='B'
for i in range(n):
    if i%2==0 and arr[i][0]=='W':
        ch[i][0]=1
        arr[i][0]='B'
    if i%2==1 and arr[i][0]=='B':
        ch[i][0]=1
        arr[i][0]='W'        
        

    for j in range(1,m):
        if arr[i][j-1]==arr[i][j]:
            ch[i][j]=1
            if arr[i][j]=='B':
                arr[i][j]='W'
            else:
                arr[i][j]='B'

Minn=100000
for i in range(n-8+1):
    for j in range(m-8+1):
        S=0
        for k in range(8):
            S=S+sum(ch[k+i][j:j+8])
        if S<Minn:
            Minn=S

arr1[0][0]='W'
for i in range(n):
    if i%2==0 and arr1[i][0]=='B':
        ch1[i][0]=1
        arr1[i][0]='W'
    if i%2==1 and arr1[i][0]=='W':
        ch1[i][0]=1
        arr1[i][0]='B'        
        
    for j in range(1,m):
        if arr1[i][j-1]==arr1[i][j]:
            ch1[i][j]=1
            if arr1[i][j]=='B':
                arr1[i][j]='W'
            else:
                arr1[i][j]='B'

for i in range(n-8+1):
    for j in range(m-8+1):
        S=0
        for k in range(8):
            S=S+sum(ch1[k+i][j:j+8])
        if S<Minn:
            Minn=S

print(Minn)

처음 내가 작성한 코드이다.

테스트케이스 모두 출력이 잘되었지만 57프로까지 검사하다가 '틀렸습니다'가 떴다.

 

 

도저히 반례를 못찾아 GPT를 사용해서 물어보니 아래와 같은 반례를 알려주었다.

 

모두 같은 색으로 이루어진 경우:

 만약 입력으로 모두 같은 색으로 이루어진 체스판이 주어진다면, 해당 코드는 항상 0을 출력할 것입니다.

하지만 반례로서, 입력으로 "WWWWWWWW"와 같이 모두 흰색으로 이루어진 8x8 체스판이 주어진다면, 결과는 0이 아닌 32가 되어야 합니다. 이 경우, 코드가 올바르게 작동하지 않습니다.

 

 

반례를 수정한 코드

n, m = map(int, input().split())

arr = [list(input()) for _ in range(n)]

def count_changes(board):
    min_changes = float('inf')
    for start_color in ['B', 'W']:
        changes = 0
        for i in range(8):
            for j in range(8):
                if board[i][j] != start_color:
                    changes += 1
                start_color = 'W' if start_color == 'B' else 'B'
            start_color = 'W' if start_color == 'B' else 'B'
        min_changes = min(min_changes, changes)
    return min_changes

min_changes = float('inf')

for i in range(n - 7):
    for j in range(m - 7):
        sub_board = [row[j:j+8] for row in arr[i:i+8]]
        min_changes = min(min_changes, count_changes(sub_board))

print(min_changes)

GPT가 짜준 반례를 보완한 코드이다.

너무 깔끔하고 가독성이 좋지만 이해하기에는 좋은 코드는 아닌것 같다.

 

 

오히려 아래 의 유튜브 강의와같은 코드가 더욱 이해하기 좋은것 같다.

https://www.youtube.com/watch?v=QhRprjs7BSs&ab_channel=%EC%8A%B9%EC%9A%B1%EC%9D%80