[백준][1018]체스판 다시 칠하기 | 파이썬

💡문제 분석 요약

MxN크기의 보드가 있다.

어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다.

이 보드를 잘라서 8x8 크기의 체스판으로 만들려고 한다.

체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다.(변을 공유하는 두 개의 사각형은 다른색으로 칠해져 있어야 한다.) 보드가 체스판처럼 칠해져 있다는 보장이 없어서, 8x8 크기의 체스판으로 잘라낸 후 몇 개의 정사각형을 다시 칠해야 한다.

8x8크기는 아무데서나 골라도 된다.

다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 만들어라.

💡알고리즘 설계

1. 입력처리N개의 문자열을 읽어 보드를 생성한다.
2. 첫 줄에 보드의 크기 N x M을 입력받는다.
3. 8x8 영역에서 칠해야 할 칸 계산 (def count_repaint)각 패턴에 대해 현재 보드와 비교하며 칠해야 할 칸의 수를 계산한다.
4. 두 패턴 중 더 적은 칸을 칠하는 경우를 반환한다.
5. x,y는 8x8 보드의 시작 좌표이다.
6. 모든 가능한 8x8 영역 탐색모든 시작점에 대해 최솟값을 갱신한다.
7. 가능한 시작 좌표( i,j)를 모두 탐색하며 각 영역의 칠하기 횟수를 계산한다.
8. 모든 경우를 계산한 후 최솟값을 출력한다.

💡코드

n,m = map(int,input().split())
board = [input() for i in range(n)]  #체스판을 입력받는다.

def count_repaint(x, y): #x,y 는 8x8보드의 시작 좌표이다.
    # (x,y)를 시작으로 하는 8x8 영역을 체스판 두 패턴과 비교하여 최소로 다시 칠해야 하는 칸의 개수를 계산
    pattern1, pattern2 = 0, 0   # 규칙 1 : 맨 왼쪽 위 칸이 검정(B)로 시작/ 규칙 2: 맨 왼쪽 위 칸이 흰색(W)로 시작
    for i in range(8): #8x8칸의 행(위아래) 탐색
        for j in range(8): #8x8칸의 얄(왼오른쪽) 탐색
            #현재 칸의 색과 패턴 비교
            if (i + j) % 2 == 0:   #짝수 칸
                if  board [x+i][y+j] != 'B':  #패턴 1은 B로 시작
                    pattern1 +=1   # 다시 칠해야 함
                if board[x+i][y+j] != 'W': # 패턴 2는 w로 시작
                    pattern2 +=1   # 다시 칠해야 함
            
            else:   # 홀수 칸
                if board[x+i][y+j] != 'W': # 패턴 1은 W로 시작
                    pattern1 += 1
                if board[x+i][y+j] != 'B': #패턴 2는 B로 시작
                    pattern2 += 1
    
    # 두 패턴 중 더 적은 칸을 칠하는 경우 선택
    return min(pattern1, pattern2)

min_repaint = float('inf')  #칠해야 할 칸의 최소값 초기화

# 가능한 모든 8x8 영역의 시작점 탐색
for i in range(n-8+1):  #행 시작점 탐색
    for j in range(m-8+1):  # 열 시작점 탐색
        #(i,j)에서 시작하는 8x8 영역의 최소 칠하기 값 갱신
        min_repaint = min(min_repaint, count_repaint(i,j))

# 최종 결과 출력
print(min_repaint)

💡시간복잡도

1. 반복문: (N-7) x (M-7) : 가능한 시작점의 개수
2. 8x8영역 탐색: 각 반복에서 64(8x8) 칸을 검사

최종 시간 복잡도:

O((N - 7) x (M-7) x 64) 최대 N=M=50 일때 : O(43 x 43 x 64) = O(118,336)

💡 틀린 이유

접근방식이 틀림

💡 틀린 부분 수정 or 다른 풀이

정답 코드를 보고 공부하였다…