1018 체스판 다시 칠하기

체스판 다시 칠하기 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	6838	2727	2277	42.553%

문제

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

하지만 지민이는 이 보드가 체스판처럼 검정/흰색 패턴이 번갈아가며 색칠해져있지 않기 때문에 고민에 빠졌다. 따라서 지민이는 8*8크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야 겠다고 생각했다. 당연히 8*8크기는 아무데서나 골라도 된다.

현재 보드의 색이 어떤지 상태가 주어질 때, 지민이가 8*8크기로 자른 뒤에 다시 칠해야하는 정사각형 개수의 최솟값을 구하는 프로그램을 작성하시오.

체스판은 각 정사각형이 검정 또는 흰색이며, 변을 공유하는 두 개의 사각형이 같은 색이 아닐 때 이다. 따라서 위 정의에 의하면 체스판의 색은 항상 두 가지가 가능한데, 하나는 왼쪽 위 코너가 흰색인 것, 검정색인 것 두가지이다.

입력

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

출력

첫째 줄에 지민이가 8*8크기로 자른 뒤에 다시 칠해야하는 정사각형 개수의 최솟값을 출력한다.

기록을 봤더니 2달전에 풀었던 문제였다.

예전의 나와 대결을 한것인데

채점 번호	아이디	문제 번호	결과	메모리	시간	언어	코드 길이	제출한 시간
12347190	rlaeogus890	1018	맞았습니다!!	29056	100	Python 3 / 수정	1455	1분 전
11328683	rlaeogus890	1018	맞았습니다!!	118212	140	PyPy3 / 수정	1366

압승했다

메모리와 시간과 코드길이가 압도적으로 빨라졌다.

스스로 일취월장했다는 느낌이 들었다.

2달전의 내 사고력과 지금의 내 사고력을 한번 체크해보자.

예전.

row, col = map( int, input().split() )

matrix = [ list(input()) for i in range(row)]

matrix_A=[] # WBWB

#matrix_B=[] # BWBW

mask1 = []

#mask2 = []

a = "B"

b = "W"

for i in range(row):

    c = a

    a = b

    b = c

    mask1=[]

    #mask2=[]

    for j in range(col):

        if j%2 ==0 : 

            if matrix[i][j] == a:

                mask1.append(True)

                #mask2.append(False)

            else:

                mask1.append(False)

                #mask2.append(True)

        else:

            if matrix[i][j] == b:

                mask1.append(True)

                #mask2.append(False)

            else:

                mask1.append(False)

                #mask2.append(True)

    

    matrix_A.append(mask1)

    #matrix_B.append(mask2)

#for i in range(row):

#    print(matrix_A[i])

def how_many_repair_in_8to8(startX,startY):

    global matrix_A

    nT = 0

    nF = 0

    for i in range(8):

        for j in range(8):

            if matrix_A[startX+i][startY+j] == True:

                nT = nT+1

            else:

                nF = nF+1

    

    return min([nT,nF])

min_repair = 50*50

for i in range(0,row-7,1):

    for j in range(0,col-7,1):

        temp = how_many_repair_in_8to8(i,j)

        if min_repair > temp:

            min_repair = temp

print(min_repair)

지금

import sys

def check(x,y):
    global bd
    global exam1
    global exam2

    res1 =0
    res2= 0
    for i in range(8):
        for j in range(8):
            if(exam1[i][j] != bd[x+i][y+j]):
                res1 +=1
            if (exam2[i][j] != bd[x + i][y + j]):
                res2 += 1
    return min( (res1,res2) )

exam1 = [ ['W','B','W','B','W','B','W','B'],
          ['B','W','B','W','B','W','B','W'],
          ['W','B','W','B','W','B','W','B'],
          ['B','W','B','W','B','W','B','W'],
          ['W','B','W','B','W','B','W','B'],
          ['B','W','B','W','B','W','B','W'],
          ['W','B','W','B','W','B','W','B'],
          ['B','W','B','W','B','W','B','W'],
          ['W','B','W','B','W','B','W','B'] ]
exam2 = [ ['B','W','B','W','B','W','B','W'],
          ['W','B','W','B','W','B','W','B'],
          ['B','W','B','W','B','W','B','W'],
          ['W','B','W','B','W','B','W','B'],
          ['B','W','B','W','B','W','B','W'],
          ['W','B','W','B','W','B','W','B'],
          ['B','W','B','W','B','W','B','W'],
          ['W','B','W','B','W','B','W','B'],
          ['B','W','B','W','B','W','B','W'] ]

row,col = map(int,input().split())

bd = [""] * row
for i in range(row):
    bd[i] = list(input())

answer = row*col

for i in range(row - 7):
    for j in range(col - 7):
        temp = check(i,j)
        answer = temp if temp < answer else answer

print(answer)

이제 DFS,BFS 등등이랑 알고리즘 풀기속도를 향상시켜야하는데... 열심히 노력해야겠다.

아맞다. 이 문제를 푸는 핵심적인 방법은

2개의 완성된 체스판을 주어진 크기의 체스판의 첫번째부터 올려서 비교해가며

수정해야할부분이 가장작을 때를 기억하는 것이 핵심이다.