[백준/Python3] 1018번. 체스판 다시 칠하기

문제

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

---

1. 첫 번째 풀이

사고 과정

뭐 이딴 문제가

 

일단 가장 단순한 방법부터 해봐야겠지.

보드를 입력받고, 맨 위에서부터 8x8 사이즈로 하나씩 잘라보고, 만들어진 보드판에서 몇 개를 바꿔야하는지 센다. 가능한 정답 배열은 2가지니, 2번씩. 이걸 끝까지 반복한다.

 

N, M이 최대 50이니 잘랐을 때 나오는 보드판은 최대 43x43개. 각 2가지니 x2, 모든 칸을 확인해본다면 64개씩.

43 x 43 x 2 x 64 = 236,672. 막 못할 정도는 아니다.

 

코드

def countChanges(board):
    whiteCount = 0
    for i in range(8):
        for j in range(8):
            if(board[i][j] != white[i][j]):
                whiteCount += 1

    blackCount = 0
    for i in range(8):
        for j in range(8):
            if(board[i][j] != black[i][j]):
                blackCount += 1

    return min(whiteCount, blackCount)

# main
n, m = map(int, input().split())

board = [list(input()) for _ in range(n)]
white = ['WBWBWBWB', 'BWBWBWBW', 'WBWBWBWB', 'BWBWBWBW', 
         'WBWBWBWB', 'BWBWBWBW', 'WBWBWBWB', 'BWBWBWBW']
black = ['BWBWBWBW', 'WBWBWBWB', 'BWBWBWBW', 'WBWBWBWB',
         'BWBWBWBW', 'WBWBWBWB', 'BWBWBWBW', 'WBWBWBWB']

minCount = 99

for i in range(n - 7):
    for j in range(m - 7):
        subBoard = [row[j : j + 8] for row in board[i : i + 8]]
        count = countChanges(subBoard)
        minCount = min(minCount, count)


print(minCount)

 

결과

 

가볍게 정답이 나왔다. 코드를 짜는데 파이썬 문법은 Gemini의 도움을 받았고, 총 30분 정도 걸린 듯하다.

파이썬에서 2차원 배열을 다루는 게 익숙치 않아 꽤 오래 걸렸다.

 

변수를 min으로 선언했다가, 함수 min과 겹쳐 함수가 작동하지 않은 이슈가 있었다. 쓸데없이 이런데선 섬세하다.

---

2. 마지막 풀이

사고 과정

정답은 맞췄지만, 아쉬움이 꽤 남는 코드. 좀 더 쉬운 방법은 없을까?

 

가장 먼저 떠올린 건, 첫칸이 흰색인 경우(이하 흰색 체스판)와 검은색(이하 검은색 체스판)인 경우, 각각의 정답이 더해서 64가 나올 것이란 거다.

어찌보면 당연한 게, 흰색 체스판을 검은색 체스판으로 만드는데 64번 변경이 필요하고, 이미 바껴진 게 있다면 그만큼 빠지는 식이니, 당연히 64를 나눠먹을 것.

 

그러니 검은색 체스판 = 64 - 흰색 체스판으로 줄일 수 있다.

 

그렇지만, 흰색 체스판 역시, 일일이 세는 건 번거롭다. 아예 입력받을 때부터 판정한다면, 쉽지 않을까?

예를 들어, 처음 N, M 크기의 체스판을 입력받을 때, W와 B로 받는 대신, 흰색 체스판으로 바꾸는데 필요한 횟수를 각 칸에 적어둔다면. 나중에 배열 슬라이싱 후에 내부 요소를 모두 더함으로써 그 값을 얻어낼 수 있지 않을까?

 

예를 들면 이런 식으로 말이다.

 

WBWBWBWB                                            0 0 0 0 0 0 0 0

BWBWBWBW                                            0 0 0 0 0 0 0 0

WBWBWBWB                                            0 0 0 0 0 0 0 0

BWBBBWBW                    ->                     0 0 0 1 0 0 0 0

WBWBWBWB                                            0 0 0 0 0 0 0 0

BWBWBWBW                                            0 0 0 0 0 0 0 0

WBWBWBWB                                            0 0 0 0 0 0 0 0

BWBWBWBW                                            0 0 0 0 0 0 0 0

 

이렇게 정수로 저장해두면, 계산이 편해지지 않을까?

 

input에 if문을 적어 비교하는 건 맘에 안 든다. 수학적으로 계산하는 방법을 찾아보자.

흰색 체스판의 경우, (0, 0)이 흰색이다. 흰색을 0으로, 검은색을 1로 적는다면

각 칸 (i, j)에서 i + j가 짝수라면 흰색, 홀수라면 검은색. 즉 짝수라면 0, 홀수라면 1이 된다.

이는 간단히 (i + j % 2)로 나타낼 수 있다.

 

이건 정답 보드고, 실제 입력은 여기에, 각 칸에 0, 1이 추가로 들어온다.

둘이 다를 경우 1을 적어야 하니, 해당 입력값을 더하고 다시 2로 나누면 될 듯 하다.

 

예를 들어, 흰색 칸(i + j % 2 = 0)에 흰색(0)이 들어왔다면, 0 + 0 % 2 = 0이 된다.

검정색(1)이 들어온다면, 0 + 1 % 2 = 1이 되며, 이는 바꿔야하는 횟수가 된다.

역으로, 검은색 칸(1)에 검은색(1)이 들어오면 나머지가 0, 흰색(0)이 들어오면 나머지는 1이 된다.

 

그러니, 만약 입력값을 W, B에서 바로 0, 1로 바꿀 수만 있다면, 보드를 만드는 건 수월하다.

 

방금 전 map 함수에 대해 공부해봤을 때, 이 함수가 자료형 변환 같은 게 아닌, 모든 요소에 특정 함수를 적용하는 함수라는 걸 배웠었다. 이걸 응용하면 되지 않을까?

...라고 생각했었는데, input 값을 전부 변환하는덴 도움이 되지만, 이번엔 현재 칸의 인덱스까지 필요하기에, 2중 for문을 이용했다.

 

enumerate 함수를 새로 배워서 써먹었는데, 리스트의 인덱스, 요소를 함께 제공해준다. 파이썬은 여러모로 편한 함수가 많은 것 같다.

코드

def charToInt(c):
    return int(c == 'B')

def countChanged(board):
    white = sum(sum(row) for row in board)
    black = 64 - white

    return min(white, black)

# main
n, m = map(int, input().split())

board = [[(i + j + charToInt(c)) % 2
         for j, c in enumerate(input())]
         for i in range(n)]

minCount = 99
for i in range(n - 7):
    for j in range(m - 7):
        subBoard = [row[j : j + 8] for row in board[i : i + 8]]
        minCount = min(minCount, countChanged(subBoard))

print(minCount)

 

결과

 

코드 변경에 약 26분이 걸렸다. Python3와 PyPy3로 각각 제출해봤는데, 상당히 빨라졌다.

 

개인적으론 로직이 깔끔해져서 맘에 든다. 변경 횟수 세는 것도 sum으로 압축됐고.

---

가장 효율적인 코드

내 코드와 비교

https://www.acmicpc.net/source/85079215

hsohilyt105님의 코드. 띄어쓰기가 없어 읽기는 불편하지만, 뜯어보면 배울 게 많다.

코드

내가 charToInt 함수를 만든 것에 비해, 이분은 ord 함수를 이용해 숫자로 만들었다.

어차피 % 2로 홀수, 짝수만 판별하면 되는 상황에, W = 87, B = 66임을 이용, black을 기준으로 나와 같은 로직을 사용한다.

 

또 r(min)의 경우, black이나 white, 둘 중 하나는 32 이하라는 걸 이용해 초기값을 32로 설정했다.

 

추가로 중요한 부분은 로직 자체에 있는데, 이분은 구간합을 사용하였다. 매번, 모든 잘라낸 보드를 전부 더하는 대신, 제외된 부분은 빼고, 추가된 부분은 더해서 값을 구하였다. 그렇기에 시간적 이점을 가져가셨다.

---

강평

브론즈 문제로 기초적인 감은 잡았으니, 이제 실버 문제로 간단한 알고리즘 + 파이썬 심화 과정을 밟으려 한다. 그래봐야 2차원 배열이나 입출력, 함수 정도지만.

 

처음 문제를 봤을 땐 "이게 뭐고..." 싶었는데, 꽤 쉬운 문제였다.