[백준 1018번] 체스판 다시 칠하기 in python

문제

지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다.

체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.

보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8×8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8*8 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.

출력

첫째 줄에 지민이가 다시 칠해야 하는 정사각형 개수의 최솟값을 출력한다.

 

예제 입력 1 

8 8
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBBBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW

예제 출력 1

1

 

 

총 7개의 예제들이 있다.

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

1018번: 체스판 다시 칠하기

 

 

---

거의 1시간이 걸려 해결은 했다.

그럼에도 불구하고 다른 분들의 코드가 더 깔끔하고 간결했다...

 

먼저 나는 소수를 찾는 문제처럼  MxN의 False 리스트 2개를 만들었다.

그 후 B와 W가 다르면, True로 넣어주는 방식으로 진행했다. (왜냐면 True가 1이니깐)

 

그 뒤 3중 for문을 사용해서 8x8 필터를 MxN에 stride=1의 방식으로 진행했다.(여기서 stride=1은 한칸씩 이동함을 의미함)

그러면서 if문으로 최소인 것을 찾아줬다.

 

import copy, math

Y,X=map(int,input().split())
lst=[input() for y in range(Y)]

start_B_lst=[[False for x in range(X)] for y in range(Y)]
start_W_lst=copy.deepcopy(start_B_lst)
start_B='B'
start_W='W'

for y in range(Y):
  for x in range(X):
    if lst[y][x]!=start_B:
      start_B_lst[y][x]=True
    if lst[y][x]!=start_W:
      start_W_lst[y][x]=True
    start_B,start_W=start_W,start_B
  if X%2==0:
    start_B,start_W=start_W,start_B

if X==8 and Y==8:
  print(min(sum(sum(start_B_lst,[])),sum(sum(start_W_lst,[]))))

else:
  min_best=math.inf
  
  for y in range(Y-7):
    for x in range(X-7):
      w_sum_temp=0
      b_sum_temp=0
      for y_8 in range(y,y+8):
        w_sum_temp+=sum(start_W_lst[y_8][x:x+8])
        b_sum_temp+=sum(start_B_lst[y_8][x:x+8])

      min_temp=min(w_sum_temp,b_sum_temp)
      if min_best>min_temp :
        min_best=min_temp

  print(min_best)

 

 

다음으로 다른 사람들이 푼 코드를 풀어봤다.

내가 생각했었던 False, True 리스트를 굳이 쓰지 않고 직접 B, W를 찾는 방식이였다.

또한 여기서 8x8필터에서 쓰는 y_8과 x_8를 더해주는데, 이 더한 값의 2를 나눈 나머지가 0이면 W로 시작한다면 W.

B로 시작한다면 B가 와야한다는 조건문을 사용했다.

반대로 나머지가 0이 아니면 W로 시작했을 땐 B가 와야하고 B로 시작했을 땐 W로 와야하는 방법을 썼다.

 

그 뒤 모든 err값들을 하나의 리스트에 넣고 마지막에 min()함수를 사용하는 것으로 끝냈다.

import math

Y,X= map(int,input().split())
lst=[input() for y in range(Y)]


errs=[]
for y in range(Y-7):
  for x in range(X-7):
    start_w_err=0
    start_b_err=0
    
    for y_8 in range(y,y+8):
      for x_8 in range(x,x+8):
        if (y_8+x_8)%2==0:
          if lst[y_8][x_8]=='B': start_w_err+=1
          if lst[y_8][x_8]=='W': start_b_err+=1
        else:
          if lst[y_8][x_8]=='W': start_w_err+=1
          if lst[y_8][x_8]=='B': start_b_err+=1
    errs.append(start_w_err)
    errs.append(start_b_err)

print(min(errs))

 

 

 

언제 쯤 저렇게 간결하고 빠르게 나올 수 있을까 ㅜㅜ