개요
- 완전 탐색을 활용하는 알고리즘 문제를 풀어보고, 기록을 남겨두는 페이지
1. 문제
"""
체스판 다시 칠하기
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
2 초 128 MB 61959 29006 23412 46.984%
문제
지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다.
어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다.
체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다.
구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다.
따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.
보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8×8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다.
당연히 8*8 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다.
둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.
출력
첫째 줄에 지민이가 다시 칠해야 하는 정사각형 개수의 최솟값을 출력한다.
"""
2. 접근 방법
- 전체 체스판을 8 * 8 크기의 부분 체스판으로 나눈다.
- 슬라이싱 된 부분 체스판의 칸별 색상을 확인한 다음에, 체스판의 규칙대로 칠해져 있는 지 확인한다. 칠해져 있지 않은 칸의 개수를 계산한다.
- 이를 모든 경우의 부분 체스판에 적용하며 확인하고, 최종적으로 가장 적게 칠해야 할 칸의 개수를 리턴하면 된다.
3. 아이디어 및 주의사항
- 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 하기 때문에, 다음 규칙을 알 수 있다. 이 풀이가 구글링했을 때 많이 나오고 더 간단하고 깔끔하다.
- row_index + column_index끼리 더했을 때 짝수라면 시작점의 색깔과 같아야 제대로 칠해진 체스판
- row_index + column_index끼리 더했을 때 홀수라면 시작점의 색깔과 달라야 제대로 칠해진 체스판
- 하지만, 처음에는 이 규칙을 찾지 못해서 CNN의 컨볼루션 연산처럼 8 * 8 크기의 필터를 정의해서 한 칸씩 옮겨가며 연산하도록 접근했다. 즉, 필터는 정답이 되는 체스판이고 실제 슬라이싱된 부분 체스판과 필터를 비교해서 가장 차이가 적은 체스판의 개수를 구하는 아이디어다.
- 필터의 좌상단 첫 칸이 W로 시작하게 된다면, 필터의 각 줄의 첫 칸은 W, B, W, B, W, B, W, B로 채워져야 정상인 필터이다.
- 필터의 각 줄 첫 칸이 W로 시작하면, 해당 줄은 W, B, W, B, W, B, W, B로 채워져야 정상인 필터이다.
- 필터의 좌상단 첫 칸이 B로 시작하게 된다면, 필터의 각 줄의 첫 칸은 B, W, B, W, B, W, B, W로 채워져야 정상인 필터이다.
- 필터의 각 줄 첫 칸이 B로 시작하면, 해당 줄은 B, W, B, W, B, W, B, W로 채워져야 정상인 필터이다.
- 이 때 좌상단 첫 칸의 실제 색상에 따라 탐색하면 안 되고, W로 시작하는 경우와 B로 시작하는 경우를 매 번 모두 검사해야 한다. 예를 들어, 좌상단 첫 칸의 실제 색상이 B로 시작한다고 하더라도 W로 시작하는 필터로 비교했을 때 더 칠해야 할 칸의 수가 작을 수 있기 때문이다.
- 백준 홈페이지에서 이 문제의 예제 입력 4를 보면, 우하단 W 칸 때문에 8 * 8 배열의 좌상단의 실제 색상이 B로 칠해져 있더라도 좌상단을 W로 다시 칠하기 시작하면 31칸만 칠하면 된다. 실제 색상대로 B로 칠하기 시작하면, 33칸을 칠해야 한다.
- 나머지는 배열 인덱스에 주의하면서 for문을 활용해 작성하면 된다.
4. 구현
# 입력
board_length, board_width = map(int, input().split())
chess_board = []
for i in range(board_length):
chess_board.append(input())
# 초기화
answer = []
subarray_length = 8 # 탐색 배열의 길이는 8로 고정
w_convolution_filter = ['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'] # 컨볼루션 연산처럼 사용할 수 있는 필터. W로 시작되는 줄에 사용
b_convolution_filter = ['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'] # 컨볼루션 연산처럼 사용할 수 있는 필터. B로 시작되는 줄에 사용
# 완전 탐색
for length_index in range(board_length - (subarray_length - 1)): # 8 * 8 배열로 슬라이싱 할 수 있는 공간을 탐색
for column_index in range(board_width - (subarray_length - 1)):
for line_start_array in [w_convolution_filter, b_convolution_filter]: # 좌상단 첫 칸을 W로 칠하기 시작할 때와 B로 칠하기 시작할 때의 개수 비교.
painting_spot_counter = 0 # 칠해야 할 칸의 개수를 기록하는 변수 선언
row_index = 0 # 8 * 8 배열의 row_index 선언
for i in range(length_index, length_index + subarray_length): # 한 줄씩 순회
if line_start_array[row_index] == 'W': # 필터의 첫 칸이 W로 시작하는 경우
convolution_filter = w_convolution_filter # 줄 별로 적용하는 필터는 W로 시작하는 필터
elif line_start_array[row_index] == 'B': # 필터의 첫 칸이 B로 시작하는 경우
convolution_filter = b_convolution_filter # 줄 별로 적용하는 필터는 B로 시작하는 필터
filter_index = 0
for j in range(column_index, column_index + subarray_length): # 한 칸씩 순회
if chess_board[i][j] != convolution_filter[filter_index]: # 체스칸의 실제 색상과 필터의 색상과 다른 경우
painting_spot_counter += 1 # 색상을 변경해야 함
filter_index += 1
row_index += 1 # 다음 줄로 이동
answer.append(painting_spot_counter) # 정답 저장
print(min(answer)) # 최솟값 출력