백준 1018.py 체스판 칠하기

1018번: 체스판 다시 칠하기

처음에 문제를 맞추긴 했지만, 시간복잡도가 컸고, 복잡한 코드로 만들었다.

다시 여러 풀이를 읽어보며 나의 풀이로 수정했다.

아이디어

먼저, 문제를 읽어보면 체스판을 만들기 위해 8 x 8로 자르고, 색을 바꾸는 경우는 크게 두 가지 나뉜다고 한다. 가장 위쪽 왼쪽값이 흰색인지, 검은색인지 이 두 가지 경우에 따라 나머지 체스판의 색이 결정된다는 것. 이 부분이 가장 큰 힌트라고 할 수 있다.

먼저 8 x 8 체스판으로 자를 수 있는 경우는 index 가 0 ~ n - 7번째 행 그리고 0 ~ m - 7번째 열 두 가지 조합의 경우(for 중복문으로 해결)로 체스판 크기로 자를 수 있다. 각가의 경우의 맨 왼쪽 위의 값에 따라 나머지 체스판의 색을 몇 개를 바꿔야하는지 결정이 되는 것.

B W B W B B B B 

W B B B B B B B 

여기서 잘 보면 가장 위이며 왼쪽 요소가 B면 행과 열의 index합이 짝수인 경우에는 값이 B와 동일해야하며,

홀수면 W 로 바꿔야한다. ex) arr[0][2] 인경우 짝수 이고 arr[0][0] 과 값이 동일해야한다.

나는 함수를 만들어 맨왼쪽 위의 값이 W인 경우와 B인 경우를 나누어 바꿔야하는 색값 count 를 리턴해서 최솟값을 찾았다.

코드

def chessMake(x,y,bOrW):
    global arr
    count = 0
        
    for i in range(x, x + 8):
        for k in range(y, y + 8):
            if (i + k) % 2 == 0:
                if arr[i][k] != bOrW:
                    count += 1
            else:
                if arr[i][k] == bOrW:
                    count += 1
    return count


if __name__ == "__main__":
    n, m = map(int,input().split())
    arr = []
    min = 2147000000
    first = 0
    # 보드판 입력 
    for i in range(n):
        arr.append(list(input()))
    # 어디를 시작점으로 8 x 8 체스판을 만들 수 있는지 모든 경우를 가져옴   
    for i in range(n - 7):
        for k in range(m - 7):
            # 체스판 가장 왼쪽 위쪽이 흰색이냐 검은색이냐 두 가지 경우
            case1 = chessMake(i,k,'W')
            case2 = chessMake(i,k,'B')
            # 색을 바꿀 수 있는 더 작은 경우의 수를 할당.
            if case1 <= case2:
                res = case1
            else:
                res = case2
            if min > res:
                min = res
    print(min)