[단계별로 풀어보기][python 3] 브루트 포스 - 체스판 다시 칠하기 (1018)

1018번: 체스판 다시 칠하기 (acmicpc.net)

1018번: 체스판 다시 칠하기

시도 1

입력받은 체스판을 그대로 8개씩 잘라서 실제로 체크무늬로 만들어보고 바꾼 수만큼 카운트를 했다.

import copy

def chess(b: list):
    count = 0
    for x in range(7):
        if b[0][x] == b[0][x+1]:
            b[0][x+1] = 'W' if b[0][x+1] == 'B' else 'B'
            count += 1
    for x in range(8):
        for y in range(7):
            if b[y][x] == b[y+1][x]:
                b[y+1][x] = 'W' if b[y+1][x] == 'B' else 'B'
                count += 1
    return count

n, m = map(int, input().split())
first = []
for i in range(n):
    first.append(list(input()))
count = []

for y in range(n-7):
    for x in range(m-7):
        temp = []
        for i in range(8):
            temp.append(copy.deepcopy(first[i][x:x+8]))
        count.append(chess(temp))

print(min(count))

결과는 틀렸다 아무래도 최솟값을 찾지 못한 모양.

시도 2

이번에는 실제로 바꾸지 않고, 시작지점의 색깔과 같은지 다른지를 비교하는 방식으로 선언해보았다.

n, m = map(int, input().split())
first = []
for i in range(n):
    first.append(input())

countA= []
for i in range(m-7):
    for j in range(n-7):
        count = 0
        for x in range(i, i+8):
            for y in range(j, j+8):
                if (x+y) % 2 != 0:
                    if first[y][x] != first[j][i]:
                        count += 1
                else:
                    if first[y][x] == first[j][i]:
                        count += 1 
        countA.append(count)

print(min(countA))

이 방법도 시도 1과 마찬가지로 최솟값을 찾지 못해 실패했다.

시도 3

최솟값을 찾기 위해 시작지점이 W일 때와 B일 때를 구분했다.

n, m = map(int, input().split())
first = []
for i in range(n):
    first.append(input())

countA= []
for i in range(m-7):
    for j in range(n-7):
        countW = 0
        countB = 0
        for x in range(i, i+8):
            for y in range(j, j+8):
                if (x+y) % 2 != 0:
                    if first[y][x] == 'W':
                        countW += 1
                    elif first[y][x] == 'B':
                        countB += 1
                else:
                    if first[y][x] == 'B':
                        countW += 1 
                    elif first[y][x] == 'W':
                        countB += 1
        countA.append(min(countW, countB))

print(min(countA))