[백준 / Python] 체스판 다시 칠하기

문제 설명

---

 

---

문제 풀이

---

우선 다른 알고리즘이 떠오르지 않아 무식하게 모든 경우의 수를 풀어내고자 했다.

체스판 사이즈만큼 모든 보드를 돌아보며 실행하면 (8 * 8) * (50 - 8 + 1) * (50 - 8 + 1)번이며 이는 1억번보다 작아 풀어낼 수 있겠다고 생각했다.

 

검은색으로 시작하는 경우와 흰색으로 시작하는 경우를 한 번에 확인하기 위해 black, white를 선언했고 row가 바뀔 때마다 색이 바뀌는 것을 보고 따로 코드로 작성해주었다.

 

이후 각 경우에서 색칠해야하는 횟수가 가장 적은 것을 최솟값으로 저장한 후 제출하였다.

---

코   드

---

import sys
N, M = map(int,sys.stdin.readline().split())
board = []

for i in range(N):
    list = [1 if x == "B" else 0 for x in sys.stdin.readline().strip()]
    board.append(list)
    
minimum = 64
for i in range(N - 7):
    for j in range(M - 7):
        black, white = 0, 1
        black_diff, white_diff = 0,0

        for x in range(i, i+8):
            black, white = white, black
            for y in range(j, j+8):
                if black != board[x][y]:
                    black_diff+=1
                if white != board[x][y]:
                    white_diff+=1
                black, white = white, black

        minimum = min(black_diff, white_diff, minimum)

print(minimum)

---

느낀점: python에 아직 적응하지 못한 것 같다.. 자꾸 C++처럼 짜려고 한다.

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

1018번: 체스판 다시 칠하기