BAEKJOON 1018

16 Jan 2020

문제

지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 MxN 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8x8 크기의 체스판으로 만들려고 한다. 체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다. 보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8x8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8x8 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.

입력

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

나의 처음 코드

print 문으로 진행상황 보려고 출력찍는 작업할 때, 굉장히 바보같은 실수로 엄청 헤맸다. 항상 집중해야함을 잊지 말아야한다;) 이 문제는 완전히 노가다 문제다. (0,0) 좌표부터 행렬을 초과하지 않게 하나씩 다 비교하고, 다 돌려보는 문제이다. 물론 3중으로 포문을 안 짠사람도 있지만, 3중 포문안에 모든걸 다 처리해줬으므로 이것도 그럭저럭 노가다 코드인 것이다. 나의 key idea는 w_first와 b_first를 만들어서 하나씩 비교해주는 것이다. 다른 내용들은 주석안에 담겨져있다.

row, col = list(map(int, input().split()))
chess = []  # 체스판을 받을 list
flag = 0  # b_first로 시작하기 위한 flag
flag2 = 1  # w_first로 시작하기 위한 flag
count = 0  # flag로 시작했을 때 최소 숫자
count2 = 0  # flag2로 시작했을 때 최소 숫자
w_first = 'WBWBWBWB'
b_first = 'BWBWBWBW'
min_count = 99999  # 최소 바꾼 횟수

# 체스판 받기
for i in range(row):
    chess.append(input())

# 총 8x8로 받을 수 있으므로, 범위는 당연히 row-7, col-7
for i in range(0, row-7):
    for j in range(0, col-7):
        for m in range(0, 8):
            # 제일 처음시작시에 b_first로 검사한다. 그 후에는 번갈아서
            flag = 0 if flag == 1 else 1
            # 제일 처음시작시에 w_first로 검사한다. 그 후에는 번갈아서
            flag2 = 0 if flag2 == 1 else 1
            for n in range(0, 8):
                #flag 컨트롤
                if flag == 0:
                    if w_first[n] != chess[m+i][n+j]:
                        count += 1
                if flag == 1:
                    if b_first[n] != chess[m+i][n+j]:
                        count += 1
                #flag2 컨트롤
                if flag2 == 0:
                    if w_first[n] != chess[m+i][n+j]:
                        count2 += 1
                if flag2 == 1:
                    if b_first[n] != chess[m+i][n+j]:
                        count2 += 1
        min_count = min(count, count2, min_count)
        #초기화 작업
        flag = 0
        flag2 = 1
        count = 0
        count2 = 0

print(min_count)

min()

def min(iterable: Iterable[_T], key: Callable[[_T], Any]=..., default: _VT): single arg(iterable)일 때는 그것들중에 가장 작은 값을 반환한다. 2개 이상의 args일 때는 가장 작은 값을 반환한다. 즉 list를 하나 넣었을 때는, 리스트중 가장 작은 값을 반환한다. 반면 예를 들어 a,b,c 가 (값/문자)이고 이것을 arg로 넣는다면, Iterable 하지 않아도 가장 작은 값을 반환한다.

같은 브루트포스(무식하게 다해보는) 방식은 별로 썩 풀어서 기분좋은 문제는 아닌것 같다. 집중력만을 요하는 문제랄까…?