Baekjoon 1018번 체스판 다시 칠하기

문제

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

걸린 시간

02 : 33 : 44

풀이

Python3

def getChess(board, row, col):
    temp = []

    # 보드와, 자르기 시작할 좌표를 받아온다.    
    for r in range(0+row, 8+row):
        for c in range(0+col, 8+col):
            temp.append(board[r][c])

    return temp

def is_change(cb, sc, i): # cb : chess board, sc : start character
    # 짝수 수일때
    if (i%8)%2 == 0:
        # 시작 문자와 같지 않으면 바꾼다
        if cb[i] != sc:
            return True
    else:
        # 시작 문자와 같으면 바꾼다
        if cb[i] == sc:
            return True

    return False

if __name__ == "__main__":
    N, M = map(int, input().split())

    board = []

    # board 를 입력받는다.
    for i in range(0, N):
        temp = list(input())
        board.append(temp)

    chess = []

    for row in range(0, N-8+1):
        for col in range(0, M-8+1):
            chess.append(getChess(board, row, col))

    # 체스판처럼 되기 위해 칠해야 하는 수를 계산하고 최소값일 경우 결과값에 저장한다. 
    result = 64
    start = ['W', 'B']
    for cb in chess: # cb : chess board
        for s in range(0, len(start)): 
            # 변경한 횟수
            count = 0

            for i in range(0, len(cb)):
                # 짝수 줄일때 
                if (i//8)%2 == 0:
                    if is_change(cb, start[s], i):
                        count += 1
                else:
                    if is_change(cb, start[s-1], i):
                        count += 1

            # 변경한 횟수가 작은 값이면
            if result > count:
                result = count

    print(result)

문제를 읽고 모든 경우의 수를 시도해봐야하는 브루트 포스 문제임을 확인했다. 하지만 전체적인 흐름도를 구상해 놓고 시작하지 않아 효율적으로 알고리즘을 작성하지 못했고 구현하는 과정에서 시간이 많이 걸렸다.

알고리즘 수정에 유독 시간이 많이 걸렸는데 반복문의 변수로 i, j, k, l 와 같은 문자를 사용했던 것이 원인이였다.