Python) BOJ 1018. 체스판 다시 칠하기
문제 링크
제한
- 시간 제한 : 2 초
- 메모리 제한 : 128 MB
문제
-
지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다.
-
체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.
-
보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8×8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8*8 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.
입력
- 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.
출력
- 첫째 줄에 지민이가 다시 칠해야 하는 정사각형 개수의 최솟값을 출력한다.
👀 풀이
- 지민이가 가지고 싶은 체스판의 크기는 8*8이기 때문에 저 크기만큼만 조사해서 그 중 가장 적은 칸을 칠하는 경우를 찾으면 된다.
- 8*8 범위에서 색칠해야 하는 칸의 개수를 구하는 함수를 만들어 슬라이딩 윈도우처럼 옮겨가며 조사한다. 그 중 가장 작은 값을 정답으로 출력한다.
전체 코드
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
board = []
for _ in range(n):
board.append(input())
# 입력받는 부분 끝
INF = 64
ans = 64
def changeColor(cur):
if cur == 'W':
return 'B'
else:
return 'W'
def checkBoard(x, y):
cur = board[x][y]
cnt = 0
for i in range(x, x+8):
for j in range(y, y+8):
if board[i][j] != cur:
cnt += 1
cur = changeColor(cur)
cur = changeColor(cur)
cnt = min(cnt, INF - cnt)
global ans
ans = min(ans, cnt)
for i in range(n-7):
for j in range(m-7):
checkBoard(i, j)
print(ans)
코드 분석
INF = 64
ans = 64
- 8*8 체스판에서 색칠해야 하는 최대 칸의 수는 64개이다. 체스판을 칠하는 경우는
W로 시작하는 경우와B로 시작하는 경우 두 가지가 있기 때문에 두 경우에 칠해야 하는 칸의 수를 모두 비교해 봐야 한다. - 이걸 2중 반복문을 두 번 돌려 구할 수도 있지만 한 가지 경우에 칠해야 하는 개수를 구한 다음에 그걸 64에서 빼면 다른 경우에 칠해야 하는 개수가 되기 때문에 이렇게 구하는 것이 훨씬 효율적이다. 그래서 무한대값으로 64를 설정한다.
def changeColor(cur):
if cur == 'W':
return 'B'
else:
return 'W'
- 다음에 나와야 하는 색으로 바꿔주는 메서드이다. 체스판은 검은색 흰색이 번갈아 칠해지니까 서로 반대로 바꿔준다.
def checkBoard(x, y):
cur = board[x][y]
cnt = 0
for i in range(x, x+8):
for j in range(y, y+8):
if board[i][j] != cur:
cnt += 1
cur = changeColor(cur)
cur = changeColor(cur)
cnt = min(cnt, INF - cnt)
global ans
ans = min(ans, cnt)
- 8*8 크기의 보드판을 탐색하며 색칠해야 하는 칸의 개수를 구하는 메서드이다.
- 보드판의 시작점 색깔을 기준으로 새로 색칠해야 하는 칸의 개수를 구한 뒤 시작점의 색깔이 반대 색으로 시작하는 경우도 살펴봐야 하기 때문에 64에서 cnt를 뺀 수와 cnt를 비교해 봐야 한다.
B와W로 시작하는 경우에서 색칠해야 하는 개수의 비교가 끝나면 정답변수와 비교해 최소값을 구한다.
for i in range(n-7):
for j in range(m-7):
checkBoard(i, j)
print(ans)
- 입력받은 보드판의 크기가 88인 경우에 한 번은 돌아야 하기 때문에 n, m에서 7을 뺀 크기만큼 탐색하도록 한다. (8을 빼버리면 입력 크기가 88인 경우에 범위값이 0이라 반복문에 안 들어감)
결과
- 시간 : 96 ms
- 메모리 : 30840 KB