BOJ 1018. 체스판 다시 칠하기 (Python)

BOJ 1018. 체스판 다시 칠하기

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

1018번: 체스판 다시 칠하기

풀이

별다른 알고리즘 생각 할 필요 없이 브루트 포스로 풀면 된다.
W로 시작하는 보드, B로 시작하는 보드를 미리 다 만들어 놓고 비교해도 되지만 난 그렇게 풀지는 않았다.

for x in range(N - 8 + 1):
    for y in range(M - 8 + 1):
        W_start = 0
        B_start = 0

보드에서 8*8 체스판을 고르는 부분이다. W_start, B_start는 각각 흰색, 검은색으로 시작했을때 몇개를 다시 칠해야 하는지 count하는 변수이다. 이것을 0으로 정의해준다.

for i in range(x, x+8):
            for j in range(y, y+8):

잘라낸 8*8체스판에서 W와 B를 판단하기 위함이다. 위의 포문에서 x, y를 정의하는데 여기에 +8 한 값까지 포문을 돌린다.

if i%2 == 0 and j%2 == 0: # 짝수 행, 짝수 열
    if board[i][j] != "W": W_start += 1
    if board[i][j] != "B": B_start += 1
if i%2 == 0 and j%2 != 0: # 짝수 행, 홀수 열
    if board[i][j] != "B": W_start += 1
    if board[i][j] != "W": B_start += 1
if i%2 != 0 and j%2 == 0: # 홀수 행, 짝수 열
    if board[i][j] != "B": W_start += 1
    if board[i][j] != "W": B_start += 1
if i%2 != 0 and j%2 != 0: # 홀수 행, 홀수 열
    if board[i][j] != "W": W_start += 1
    if board[i][j] != "B": B_start += 1

처음부터 적으려면 헷갈려서, 주석달려있는 줄부터 적고 시작했다.

if문 안에 W로 시작하는 경우와 B로시작하는 경우 모두를 계산해주었다. 나도 처음부터 코드를 다 작성한게 아니고, 연습장에 써가면서 했다. 너무 헷갈려서.. 행과 열도 헷갈렸다. ㅋㅋㅋ 이렇게 써놓고 하면 덜 헷갈린다.

차례대로 차근차근 구해주면 된다.

 

계산이 다 끝나면

result = min(result, W_start, B_start)

최솟값을 갱신해준다.

 

생각 자체는 어려운 문제는 아니였는데, 좌표변수가 하나 꼬이기 시작하면 답이 없다. for문이 네개나 중첩되기때문에 헷갈린다. 처음부터 다 써내려가려고 하지 말고 큰 줄기부터 써주면 덜 헷갈리는것 같다.

 

전체 소스코드

import sys

N, M = map(int, input().split())
board = []
result = sys.maxsize

for i in range(N):
    board.append(sys.stdin.readline().rstrip())

for x in range(N - 8 + 1):
    for y in range(M - 8 + 1):
        W_start = 0
        B_start = 0
        for i in range(x, x+8):
            for j in range(y, y+8):
                if i%2 == 0 and j%2 == 0: # 짝수 행, 짝수 열
                    if board[i][j] != "W": W_start += 1
                    if board[i][j] != "B": B_start += 1
                if i%2 == 0 and j%2 != 0: # 짝수 행, 홀수 열
                    if board[i][j] != "B": W_start += 1
                    if board[i][j] != "W": B_start += 1
                if i%2 != 0 and j%2 == 0: # 홀수 행, 짝수 열
                    if board[i][j] != "B": W_start += 1
                    if board[i][j] != "W": B_start += 1
                if i%2 != 0 and j%2 != 0: # 홀수 행, 홀수 열
                    if board[i][j] != "W": W_start += 1
                    if board[i][j] != "B": B_start += 1
        result = min(result, W_start, B_start)

print(result)