[백준] 1018 체스판 다시 칠하기 - 파이썬

1018번: 체스판 다시 칠하기

---

초기코드

import sys

def count(board, x, y, color):
  count = 0
  for i in range(x, x + 8):
    for j in range(y, y + 8):
      if board[i][j] != color: count += 1 
      if j != y + 7:
        color = 'B' if color == 'W' else 'W'
  return count

n, m = map(int, input().split())
board = [0] * n
for i in range(n):
  board[i] = list(sys.stdin.readline())
  
min_cnt = n * m
for x in range(n - 8 + 1):
  for y in range(m - 8 + 1):
    b_cnt = count(board, x, y, 'B') 
    w_cnt = count(board, x, y, 'W')
    cnt = b_cnt if b_cnt < w_cnt else w_cnt
    if cnt < min_cnt:
      min_cnt = cnt

print(min_cnt)

count()함수는 색을 다시 칠해야 하는 곳을 세주는 함수

 

다음과 같은 예제가 있다고 하면 어떤 자리(홀수, 짝수)의 B를 W로 바꾸느냐에 따라서 칠하는 개수가 달라진다.

BBBBBBBB  
BBBBBBBB  
BBBBBBBB  
BBBBBBBB  
BBBBBBBB  
BBBBBBBB  
BBBBBBBB  
BBBBBBBW

 

만일 첫째줄에서의 짝수 자리를 W로 바꾼다고 하면 모든 줄에서 4개씩 바꾸다가

BBBBBBBB  4
BBBBBBBB  4
BBBBBBBB  4
BBBBBBBB  4
BBBBBBBB  4
BBBBBBBB  4
BBBBBBBB  4

BBBBBBBW

 

마지막 줄에서는 WBWBWBWB로 바꿔야 하므로 5자리가 바뀌어서 총 바뀌는 개수는 33

 

하지만 첫째줄에서의 홀수 자리를 W로 바꾼다고 하면

BBBBBBBB  4

BBBBBBBB  4
BBBBBBBB  4
BBBBBBBB  4
BBBBBBBB  4
BBBBBBBB  4
BBBBBBBB  4
BBBBBBBW

 

마지막 줄에서는 BWBWBWBW로 바꾸면 되므로 3자리만 바뀌어서 총 바뀌는 개수는 31

 

따라서 여기서는 color가 'W'로 전달되는 경우가 칠해야 하는 개수가 더 적다. 

이런식으로 count의 개수를 계속 구하면서 최소로 칠해야 하는 경우를 구했다.

 

그런데 사실 시작점이 바뀔 때마다 count 함수를 두 번 호출하니까 비효율적이라 생각해서 다른 사람들의 코드를 참고해서 아래와 같이 다시 작성했다. 

 

import sys

n, m = map(int, input().split())
board = [0] * n
for i in range(n):
  board[i] = list(sys.stdin.readline())
  
cnt = []
for i in range(n - 8 + 1):
  for j in range(m - 8 + 1):
    b_cnt = 0
    w_cnt = 0
    for x in range(i, i + 8):
      for y in range(j, j + 8):
        if (x + y) % 2 == 0:
          if board[x][y] != 'W':
            w_cnt += 1
          if board[x][y] != 'B':
            b_cnt += 1
        else:
          if board[x][y] != 'B':
            w_cnt += 1
          if board[x][y] != 'W':
            b_cnt += 1
    cnt.append(w_cnt)
    cnt.append(b_cnt)

print(min(cnt))

 

그런데 기존에 작성한 게 시간이 더 짧게 걸린다. 다시 여러번 채점해보니 거의 비슷한 것 같다. 시간 복잡도에서 그렇게 큰 차이는 없는 건가? 계산을 잘 못하겠다..

 

아무튼 두 번째 방법에서 if (x + y) % 2 == 0 이 방법으로 구현한 게 더 좋은 것 같아서 나중에 안보고 저 방법대로 다시 풀어볼 예정이다. if (x + y) % 2 == 0를 사용한 이유는 https://god-gil.tistory.com/62 이 분 블로그를 참고하면 좋다.