[코테]99클럽 코테 스터디 22일차 TIL 백준 1018 체스판 다시 칠하기

테스트 크기를 보고 딱 브루트포스알고리즘이겠다~ 해서 전부 다 탐색하는걸로 풀었는데 좀 오래걸렸다... 더 예쁘고 효율적인 풀이도 공부해야겠다 

풀이 순서는 

• 8*8 윈도우 모두 구하기 
• 정답 체스판 2가지 구현해놓기 
• 3중 for문으로 모든 윈도우에 대하여 정답과 다른 문자 카운트하기
• 최솟값 구하기 

인데, 조금 더 예쁜 풀이도 찾아보았다..

내풀이 

import sys

read = sys.stdin.readline

N, M = map(int,read().split())

chess_map = []

for _ in range(N):

    chess_map.append(read().rstrip())

windows = []

for i in range(N-7):

    window_xs = chess_map[i:i+8]

    for j in range(M-7):

        window = [w[j:j+8] for w in window_xs]

        windows.append(window)

answer1 = []

for i in range(8):

    if i % 2 == 0:

        answer1.append('WBWBWBWB')

    else:

        answer1.append('BWBWBWBW')

answer2 = []

for i in range(8):

    if i % 2 == 0:

        answer2.append('BWBWBWBW')

    else:

        answer2.append('WBWBWBWB')

result = sys.maxsize

for window in windows:

    cnt_1 = 0

    cnt_2 = 0

    for i in range(8):

        for j in range(8):

            if window[i][j] != answer1[i][j]:

                cnt_1 += 1

            if window[i][j] != answer2[i][j]:

                cnt_2 += 1

    result = min(cnt_1,cnt_2,result)

           

print(result)

예쁜 풀이

import sys

def min_paint(chessboard, x, y):

    # 체스판 패턴 2가지 생성

    pattern1 = [ "BWBWBWBW", "WBWBWBWB" ] * 4

    pattern2 = [ "WBWBWBWB", "BWBWBWBW" ] * 4

    count1, count2 = 0, 0

    for i in range(8):

        for j in range(8):

            if chessboard[x + i][y + j] != pattern1[i][j]:

                count1 += 1

            if chessboard[x + i][y + j] != pattern2[i][j]:

                count2 += 1

    return min(count1, count2)

def solution():

    n, m = map(int, sys.stdin.readline().split())

    board = [sys.stdin.readline().strip() for _ in range(n)]

    min_changes = float('inf')

    for i in range(n - 7):

        for j in range(m - 7):

            min_changes = min(min_changes, min_paint(board, i, j))

    print(min_changes)