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

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

문제

• M*N 크기의 보드 중 색이 잘못 칠해져 있는 정사각형을 다시 칠한다.
• 8*8로 잘라서 체스판을 만들때 색을 다시 칠하는 개수가 최소
• 최소를 찾기 위해선 결국 8*8로 잘랐을때 칠해야하는 정사각형의 개수를 모두 구해야 함

입력

• 첫째 줄, N과 M
• 다음 줄, N개의 줄로 이루어진 보드의 각 행의 상태

출력

• 다시 칠해야하는 정사각형 개수의 최솟값

풀이

• 8 * 8로 묶어서 잘못 색이 칠해져있는 모든 칸의 수를 찾는 프로그램을 작성해야하는데 여기서 주의할 점이 다음과 같다.

  • 8x8을 매번 방문하면서 잘못 색이 칠해져 있는 칸을 찾으면 실행 시간이 너무나 길어진다.
  • 왼쪽 맨 위가 흰색인 경우와 검은색인 경우를 두 가지 모두 고려해야한다.

• 따라서 다음과 같은 순서로 풀이를 진행했다.

  	1. 왼쪽 맨 위가 흰색인 경우와 검은색인 경우, 색을 다시 칠해야하는 칸을 구별한다.
  	2. 8x8로 묶어서 해당 범위 안에 잘못 색이 칠해져있는 모든 정사각형의 수를 구한다.
  	3. 정사각형의 수 후보군들 중, 최소가 되게 하는 값을 선택한다.

• 색을 다시 칠해야하는 칸을 1로 표현
  - 1로 표현한 이유는 추후 다시 칠해야하는 정사각형의 합을 구할 때 sum 함수를 통해 한번에 구하기 위해 1로 표시한다.

for i in range(N):
    for j in range(M):
        # i + j가 짝수인 칸
        if (i + j) % 2 == 0:
            if chessboard[i][j] == "B":
                chg_w[i][j] = 1
            else:
                chg_b[i][j] = 1
        # i + j가 짝수인 칸
        elif (i + j) % 2 == 1:
            if chessboard[i][j] == "W":
                chg_w[i][j] = 1
            else:
                chg_b[i][j] = 1

• 8x8로 묶어 해당 범위 안에 잘못 칠해져 있는 모든 정사각형의 수를 계산
  - 두 가지 경우 중 최소값을 결과 리스트에 추가
  - 결과 리스트 값 중 최소값이 실제로 결과로 출력되는 값

ans = []
for i in range(N - 8 + 1):
    for j in range(M - 8 + 1):
        s_w = s_b = 0
        for k in range(8):
            s_w += sum(chg_w[i + k][j : j + 8])
            s_b += sum(chg_b[i + k][j : j + 8])
        ans.append(min(s_w, s_b))

오류 및 해결

• 원래 2차원 배열 슬라이싱을 한번에 해서 sum을 구하려고 했다.
• numpy를 이용해 2차원 배열 슬라이싱을 하려고 했으나, 백준에서는 외부 모듈을 추가적으로 지원하지 않는다고 해서 사용하지 않고 반복문 안에 행 슬라이싱을 진행하는 방식으로 구현했다.
• numpy를 사용한다면 다음과 같이 2차원 배열 슬라이싱과 합계를 더 쉽게 구할 수 있다.

import numpy as np

chg_w = np.array(chg_w)
chg_b = np.array(chg_b)

ans = 64
for i in range(N - 8 + 1):
    for j in range(M - 8 + 1):
        s_w = s_b = 0
        s_w = np.sum(chg_w[i : i + 8, j : j + 8])
        s_b = np.sum(chg_b[i : i + 8, j : j + 8])
        ans = min(ans, s_w, s_b)

코드

N, M = map(int, input().split())

chessboard = []
for _ in range(N):
    chessboard.append(input())

chg_w = [[0 for _ in range(M)] for _ in range(N)]
chg_b = [[0 for _ in range(M)] for _ in range(N)]

for i in range(N):
    for j in range(M):
        # i + j가 짝수인 칸
        if (i + j) % 2 == 0:
            if chessboard[i][j] == "B":
                chg_w[i][j] = 1
            else:
                chg_b[i][j] = 1
        # i + j가 짝수인 칸
        elif (i + j) % 2 == 1:
            if chessboard[i][j] == "W":
                chg_w[i][j] = 1
            else:
                chg_b[i][j] = 1


ans = []
for i in range(N - 8 + 1):
    for j in range(M - 8 + 1):
        s_w = s_b = 0
        for k in range(8):
            s_w += sum(chg_w[i + k][j : j + 8])
            s_b += sum(chg_b[i + k][j : j + 8])
        ans.append(min(s_w, s_b))
        
""" 
#numpy를 사용한 경우

import numpy as np

chg_w = np.array(chg_w)
chg_b = np.array(chg_b)

ans = 64
for i in range(N - 8 + 1):
    for j in range(M - 8 + 1):
        s_w = s_b = 0
        s_w = np.sum(chg_w[i : i + 8, j : j + 8])
        s_b = np.sum(chg_b[i : i + 8, j : j + 8])
        ans = min(ans, s_w, s_b)

print(ans)
"""