💡 [BOJ 1018] 체스판 다시 칠하기

목차

문제) https://www.acmicpc.net/problem/1018

1018번: 체스판 다시 칠하기

 

[내 풀이]

python

닫기 줄바꿈

import sys

N, M = map(int, sys.stdin.readline().split(" "))	# 최초 보드의 행,열 갯수(N, M) 입력
board = list()
ans = 64	# 정답이 될 수 있는 가장 큰 값은 64
case1 = [[0 for i in range(8)] for j in range(8)]
case1[0] = case1[2] = case1[4] = case1[6] = "BWBWBWBW"	# 문제에서 명시되었듯, 체스판이 될 수
case1[1] = case1[3] = case1[5] = case1[7] = "WBWBWBWB"	# 있는 case는 두가지이다. 그 중 하나.

for y_input in range(N):
​​​​board.append(sys.stdin.readline())

def func(x, y, flag):	# board의 (x, y)좌표(좌측상단 기준)
​​​​global board	# 로부터 우하향 8*8 칸을 체스판으로 만들기 위한 변환 횟수 return
​​​​ret = 0
​​​​if flag == 1:
​​​​​​​​for j in range(8):
​​​​​​​​​​​​for i in range(8):
​​​​​​​​​​​​​​​​if board[y + j][x + i] != case1[j][i]:
​​​​​​​​​​​​​​​​​​​​ret += 1
​​​​if flag == 2:
​​​​​​​​for j in range(8):
​​​​​​​​​​​​for i in range(8):
​​​​​​​​​​​​​​​​if board[y + j][x + i] == case1[j][i]:
​​​​​​​​​​​​​​​​​​​​ret += 1
​​​​return ret

for y in range(N - 8 + 1):	# case1, case2로 만들 때 최소값 = ans
​​​​for x in range(M - 8 + 1):
​​​​​​​​ans = min(ans, func(x, y, 1), func(x, y, 2))

print(ans)

 

[Comment]

(case1)

BWBWBWBW

WBWBWBWB

BWBWBWBW

WBWBWBWB

BWBWBWBW

WBWBWBWB

BWBWBWBW

WBWBWBWB

 

(case2)

WBWBWBWB

BWBWBWBW

WBWBWBWB

BWBWBWBW

WBWBWBWB

BWBWBWBW

WBWBWBWB

BWBWBWBW

 

두 케이스를 만들기 위한 변환의 횟수를 비교하기 위해,

case1을 이차원리스트로 직접 만들고 셀 하나하나 비교하는 방법을 사용했다.

무식해보일수는 있지만 정석적인 브루트포스(brute-force) 알고리즘 해법이다.