백준 1018: 체스판 다시 칠하기 Python (Brute Force)

 

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

1018번: 체스판 다시 칠하기

 

def check_chess(arr):
    cnt1 = cnt2 = 0
    # 맨 첫번째 값이 W로 시작하는 경우
    for i in range(8):
        for j in range(8):
            if i % 2 == 0:
                if (j % 2 == 0 and arr[i][j] == "B") or (j % 2 and arr[i][j] == "W"):
                    cnt1 += 1
            else:
                if (j % 2 == 0 and arr[i][j] == "W") or (j % 2 and arr[i][j] == "B"):
                    cnt1 += 1
    # 맨 첫번째 값이 B로 시작하는 경우
    for i in range(8):
        for j in range(8):
            if i % 2 == 0:
                if (j % 2 == 0 and arr[i][j] == "W") or (j % 2 and arr[i][j] == "B"):
                    cnt2 += 1
            else:
                if (j % 2 == 0 and arr[i][j] == "B") or (j % 2 and arr[i][j] == "W"):
                    cnt2 += 1
    return min(cnt1, cnt2)


N, M = map(int, input().split())    # N: 행, M: 열
chess = [list(input()) for _ in range(N)]

min_value = 987654321
# 8*8 체스판 꺼내기
for n in range(N-7):    # 8*8 체스판의 행
    for m in range(M-7):    # 8*8 체스판의 열
        arr = []
        for i in range(n, n+8):
            arr.append(chess[i][m:m+8])
        # print(arr)
        value = check_chess(arr)
        if min_value > value:
            min_value = value
print(min_value)

 

우선 N, M 값과 체스판 행렬을 입력으로부터 가져왔다.

최소값을 구하기 때문에 결괏값의 초기값은 아주 큰 값으로 설정해두었다.

입력으로 주어진 체스판을 8*8 크기의 체스판으로 쪼개는 것이기 때문에 행의 경우에는 0, 1, ..., N-8까지, 열의 경우에는 0, 1, ..., M-8의 인덱스까지 체스판이 꺼내진다.

나는 기존 체스판에서 나올 수 있는 8*8 체스판들을 하나씩 꺼내서 함수에 넣으려고 했는데, 2차원 행렬에서 슬라이싱을 할 수가 없었다.

따라서 빈 행렬을 만들고 열을 슬라이싱한 것을 8개의 행만큼 append 시키는 방법으로 새로운 8*8 체스판을 만들었다.

 

그 다음은 check_chess라는 함수에 새롭게 만든 체스판 행렬을 넣고 얻은 값을 결괏값과 비교해서 더 작은 값을 결괏값에 저장한 후 출력한다.

 

check_chess 함수의 원리는 다음과 같다.

먼저, 체스판의 첫 번째 값(즉, arr[0][0])이 B일 경우와 W일 경우로 나눈다

1. 첫 번째 값이 B일 경우
   1. 행 인덱스가 0, 2, 4, 6일 때
      • 열 인덱스가 0, 2, 4, 6이면 B
      • 열 인덱스가 1, 3, 5, 7이면 W
   2. 행 인덱스가 1, 3, 5, 7일 때
      • 열 인덱스가 0, 2, 4, 6이면 W
      • 열 인덱스가 1, 3, 5, 7이면 B
2. 첫 번째 값이 W일 경우
   1. 행 인덱스가 0, 2, 4, 6일 때
      • 열 인덱스가 0, 2, 4, 6이면 W
      • 열 인덱스가 1, 3, 5, 7이면 B
   2. 행 인덱스가 1, 3, 5, 7일 때
      • 열 인덱스가 0, 2, 4, 6이면 B
      • 열 인덱스가 1, 3, 5, 7이면 W

다르게 말하면, 위에 해당하지 않는 경우에는 체스판의 색을 바꿔야 한다는 말과 같다.

따라서 첫 번째 값에 따라 바꿔야 하는 체스판의 색을 구하고, 두 개 중에 작은 값을 반환한다.

 

 

덧붙이자면, 처음 생각은 arr[0][0] 값을 보고 케이스를 정하자는 것이었는데 이렇게 하면 예제4에서 결과값이 31이 아닌 32가 나온다.

이유를 분석해봤는데, 예제 4의 경우에는 8*8 체스판의 맨 마지막이 W이다. 이렇게 되면 arr[0][0] = B로 생각했을 때와 arr[0][0] = W로 생각했을 때의 결과값이 다르게 나오는데, 나는 아예 지정을 해버리기 때문에 값이 틀렸었다.

따라서 기존 arr[0][0] 값을 사용하는 것이 아니라 아예 새롭게 두 경우 모두를 고려해야 했다.

 

이 문제는 백준 실버 문제이지만 문제 지문을 이해하는 데 시간이 걸려서 항상 볼 때마다 못 풀고 넘어갔었다.

이번 스터디 때 문제를 풀어보면서 생각보다 어렵지 않게 풀 수 있었고, 앞으로는 좀 더 경계심을 풀고 문제에 접근해봐야겠다.