BOJ 1018 - 체스판 다시 칠하기

요구사항

• MN개의 단위 정사각형으로 나누어져 있는 MxN 크기의 체스보드
• 어떤 정사각형은 검은색, 나머지는 흰색
• 이 보드를 잘라서 8x8 크기의 체스 보드를 만든다.

체스판의 요건

• 검은색과 흰색이 번갈아(변을 공유하는 두 개의 사각형은 다른 색으로)
• 체스판을 칠하는 경우는 두 가지
  • 맨 왼쪽 위 칸이 흰색
  • 맨 왼쪽 위 칸이 검은색
• 8x8 로 자른 후에 몇 개의 정사각형을 추가로 칠한다.

다시 칠해야 하는 정사각형의 최소 개수?

입력

M N
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBBBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW

• 첫째 줄에 N과 M이 주어진다. (50 >= N,M >= 8)
• 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어짐
• B는 검은색, W는 흰색

출력

1

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

문제 첫인상

• 체스판을 칠하는 문제구나
• 아하 왼쪽 위가 어떤 색인지에 따라 달라지겠군 오호
• 어떻게 자르지 -> 최소를 발견하려면 한칸씩 탐색해야될듯?
• 이거 브루트포스일수밖에 없는거같기도
• 8x8 잘라서 탐색하는 함수 -> min 갈아치우면서 최솟값 Index를 저장하는 방식이 좋지 않을까 나중에 탐색할 일 없으니까
• 번갈아서 나오는 경우가 두가지 있는데 그 두가지의 경우를 모두 고려 어떠심
• 값을 어떻게 저장할까 -> 왼쪽 위칸에 해당되는 것을 인덱스로 하여 2차원배열로 값 집어넣기?
• 어 검은색으로 시작/흰색으로 시작 이렇게 문자열 두개 만들어서 한줄씩 번갈아 비교하는거 어떰

슈도코드

• 입력받고 수행하는 main

def main(): 
	#입력받기 
    for #2중 
    	#자르고 
        doCutBoard() 
        #탐색 
        compareBoard() 
    #end for

• 8x8로 잘라 검색하도록 하는 것

def doCutBoard(): 
	cutBoard = [] 
    for #8개씩 잘라서 
    	cutBoard.append() 
    return cutBoard

• 비교해서 최솟값 찾기

def compareBoard(): 
	white = "WBWBWBWB" 
    black = "BWBWBWBW" 
    w = 0 
    b = 0 
    for i in range(8): 
    	for j in range(8): 
        # 문자열이랑 번갈아 비교하여 다른 경우 += 1 
    return min([w,b])

구현

# 세로(행), 가로(열)
def main():
  n, m = map(int,input().split())
  board = []
  minimumNum = 1000
  for _ in range(n):
    board.append(input())

  for i in range(0,n-8+1):
    for j in range(0,m-8+1):
      cutBoard = doCutBoard(board, i, j)
      minimumNum = min(minimumNum,compareBoard(cutBoard))

  print(minimumNum)



# 8x8 로 나누고
def doCutBoard(entireBoard, row, col):
  cut8Board = [];
  for i in range(row, row+8):
    cut8Board.append(entireBoard[i][col:col+8])
  return cut8Board

소감

예전에 풀 땐 되게 어려운 문제라고 생각했었는데, 하나씩 요구사항 잘라보고 잘 생각해보니까 이젠 풀린다.
뿌듯..감사..그 사이 무슨 일이 있었던거지

이것이...성장..?

꾸준히 풀어보자 그것만이 살길~