1018. 체스판 다시 칠하기 (파이썬)

1018번: 체스판 다시 칠하기

1018번: 체스판 다시 칠하기

문제

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

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

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

입력

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

출력

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

최적화(최종 답):

먼저 첫번째 줄에서 보드의 크기를 정수의 값으로 받아온다. 그 다음에 나오는 보드를 한 줄씩 입력받는다.

ex_y_num, ex_x_num = map(int,input().split())

board_lst=list() #가져온 보드

for i in range(ex_y_num):
  board_lst.append(input())

my_color = [] #칠해야 하는 칸의 개수

 

그 다음 보드를 8*8 크기에 맞게 한 줄씩 잘라가며 for 문을 돌려서 확인한다. 주의할 것은 가로축과 세로축이 어디인지 잘 확인하는 것이다.

for o in range(ex_x_num-7): #가로축
  for p in range(ex_y_num-7): #세로축
    #체스판 완성
    first_w = 0
    first_b = 0
    for y in range(p,p+8): #세로축
      for x in range(o,o+8): #가로축
        if (y + x) % 2 == 0: # 짝수,짝수/홀수,홀수
          if board_lst[y][x] == "B":
            first_w+=1
          else:
            first_b+=1
        else: #짝수, 홀수/홀수, 짝수
          if board_lst[y][x] == "W":
            first_w+=1
          else:
            first_b+=1
        
    my_color.append(first_w)
    my_color.append(first_b)
 

print(min(my_color))

 

문제에서 말한 것처럼 보드의 젤 왼쪽 칸이 “B”인지 “W”인지에 따라 체스판을 칠할 수 있는 경우의 수는 단 2가지이다. 그래서 변수가 first_w와 first_b 두개가 필요하다.

체스판을 행렬처럼 본다고 했을 때, board[0][0]이 검은색이라면 보드의 젤 왼쪽 칸이 흰색으로 칠해져야 하는 경우의 first_w 변수에 1을 더해야 할 것이고, 보드의 젤 왼쪽 칸이 검은색으로 칠해져야 하는 경우의 first_b 변수에 1을 더해야 할 것이다.

같은 색은 한 칸씩 떨어져서 칠해지므로, 검은 색을 예로 들었을 때 [0][0], [0][2], [0][4] … [1][1], [1][3] 순으로 칠해쳐야 한다. 이는 짝수,짝수 이거나 홀수, 홀수 의 경우이다. 다시 말해 두 수를 더해 모두 짝수라는 뜻이고, 이것은 if (y + x) % 2 == 0: 로 판별 가능하다.

잘못된 코드:

문제에 제시된 예시를 넣어보았을 때 로컬에서는 작동했지만 백준 사이트에 제출했을 때 작동하지 않았다(런타임 에러 Indexerror).

ex_input = input()
ex_lst = ex_input.split()
ex_y_num = int(ex_lst[0])
ex_x_num = int(ex_lst[1])

board_lst=ex_lst[2:len(ex_lst)+1] **#가져온 보드**

chest_lst=[] **# 8*8로 자를 체스판**
my_color = [] **#칠해야 하는 칸의 개수**
num = 0 #my_color의 요소

for o in range(ex_x_num-7): **#가로축**
  for p in range(ex_y_num-7): **#세로축**
    for k in range(p,p+8):
      chest_lst.append(board_lst[k][o:o+8])
    
    **#체스판 완성**
    if chest_lst[0][0]=="B":
      for y in range(8): **#세로축**
        for x in range(8): **#가로축**
          if (y%2==0 and x%2==0) or (y%2==1 and x%2==1): **# 짝수,짝수/홀수,홀수**
            if chest_lst[y][x] == "B":
              pass
            else:
              num += 1
          elif (y%2==0 and x%2==1) or (y%2==1 and x%2==0): **#짝수, 홀수/홀수, 짝수**
            if chest_lst[y][x] == "W":
              pass
            else:
              num+=1
      my_color.append(num)
      num=0
    elif chest_lst[0][0]=="W":
      for y in range(8):
        for x in range(8):
          if (y%2==0 and x%2==0) or (y%2==1 and x%2==1): **# 짝수,짝수/홀수,홀수**
            if chest_lst[y][x] == "W":
              pass
            else:
              num += 1
              
          elif (y%2==0 and x%2==1) or (y%2==1 and x%2==0): **#짝수, 홀수/홀수, 짝수**
            if chest_lst[y][x] == "B":
              pass
            else:
              num+=1

      my_color.append(num)
      num=0
    
    chest_lst.clear()

print(min(my_color))

문제점 1. 백준 input값에 줄바꿈이 있을 때 그대로 값을 복사해서 로컬에서 테스트하면 작동하지 않는다.

첫번째 줄의 8 8 을 입력하고 다음 줄에 차례로 문자열을 한 줄씩 입력가능하도록 만들어야 한다.

 

문제점 2. 비효율적인 코드

체스판의 맨 왼쪽 칸이 “W”일 때와 “B”일때를 나눠서 코드가 길어짐

고친 부분(백준 정답처리):

• map(function, iterable)

ex_y_num, ex_x_num = map(int,input().split())

board_lst=list() #가져온 보드

for i in range(ex_y_num):
  board_lst.append(input())

chest_lst=[] # 8*8로 자를 체스판
my_color = [] #칠해야 하는 칸의 개수

 

• 불필요한 코드

for o in range(ex_x_num-7): #가로축
  for p in range(ex_y_num-7): #세로축
    for k in range(p,p+8):
      chest_lst.append(board_lst[k][o:o+8])
    #체스판 완성

나는 보드를 잘라서 체스판을 만들어 두고 칠할 칸의 개수를 계산했다. 그렇지만 보드를 ‘자를’ 필요가 없었다. 한 줄씩 계산하면 되니까!

 

• 언더바(_)사용: 변수를 따로 설정해주지 않아도 반복할 수 있다.

for _ in range(N):
original.append(input())

 

*완성된 코드는 깃허브에 올려두었습니다

깃허브 코드

GitHub - Ronnie-hh/Baekjoon: Baekjoon programming practices and the answers