[알고리즘] 완전탐색, 브루트 포스 백준 1018번 - 체스판 다시 칠하기

# 입력받은 체스판
N, M = map(int, input().split())
origin_chess = [list(input()) for _ in range(N)]

# 흰색으로 시작하는 체스판
w_chess = [
    ['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'],
    ['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'],
    ['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'],
    ['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'],
    ['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'],
    ['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'],
    ['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'],
    ['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W']
]

# 검은색으로 시작하는 체스판
b_chess = [
    ['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'],
    ['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'],
    ['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'],
    ['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'],
    ['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'],
    ['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'],
    ['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'],
    ['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B']
]

min_chess = 64  # 최대로 칠해야 할 체스의 개수는 64개

# 잘라낸 체스판 만들기: new_chess
for i in range(0, N-7):
    for j in range(0, M-7):
        new_chess = []
        new_chess.append(origin_chess[i][j:j+8])
        new_chess.append(origin_chess[i+1][j:j+8])
        new_chess.append(origin_chess[i+2][j:j+8])
        new_chess.append(origin_chess[i+3][j:j+8])
        new_chess.append(origin_chess[i+4][j:j+8])
        new_chess.append(origin_chess[i+5][j:j+8])
        new_chess.append(origin_chess[i+6][j:j+8])
        new_chess.append(origin_chess[i+7][j:j+8])

        # 제대로 색칠해진 체스판과 잘라낸 체스판 비교
        w_count = 0
        b_count = 0
        for x in range(8):
            for y in range(8):
                if w_chess[x][y] != new_chess[x][y]:
                    w_count += 1
                if b_chess[x][y] != new_chess[x][y]:
                    b_count += 1
        min_count = min(w_count, b_count)

        if min_count < min_chess:
            min_chess = min_count

        # 비교가 끝나면 clear()
        new_chess.clear()

print(min_chess)

풀이과정

1. 입력받은 체스를 origin_chess에 [N][M] 형태로 넣는다.
2. 잘라낸 체스와 제대로 칠해진 체스를 비교하기 위해 흰색으로 시작하는 체스판, 검은색으로 시작하는 체스판을 배열로 만든다.
3. 잘라질 체스판의 크기는 8*8 임으로 (0 ~ N-7) AND (0 ~ M-7)로 이중 for문을 돌린다.
4. 잘려진 체스판과 제대로 칠해진 체스판을 비교한다.
5. 흰색으로 칠해진 체스판과 검은색으로 칠해진 체스판에서 각각 새로 칠해야 할 체스를 w_count, b_count에 입력받아 최소 값을 구한다.
6. 한 번 잘려진 체스판은 다음 잘려질 체스판을 위해 clear()한다.