📑문제
n*m 크기의 보드에 체스판을 만들려한다. 변을 공유하는 사각형을 다른 색으로 칠해져있어야할 때 다시 색칠해야하는 정사각형의 수가 가장 작은 경우를 찾자
💡 핵심
다시 색칠할 필요가 있는지 체크하는 알고리즘
첫번째로 고민되었던 것이 다시 색칠할 필요가 있는. 즉 흰흰 or 검검으로 연속적으로 색칠되어있는 면에 대해서 어떻게 처리를 할까였다. 가장 먼저 떠오른 것은 담겨져있는 배열이 board라 하였을 때 board[0][0] == board[0][1] 의 경우 다시 색칠할 필요가 있도록 조건문을 구상할 생각을 하였다. 하지만 이렇게 했을 경우에 문제는 BBBW에서 2개를 색칠할 필요가 있다고 할텐데 사실 2번째 B만 W로 고치면 이상이 없기에 색칠할 개수를 올바르게 찾지 못하였다.
=> 이를 해결하기 위해 가장 단순하게 해당 배열에 하나 하나 접근해서 그 부분이 'W' 인지 'B' 인지를 확인하는 방식으로 진행하여 해결하였다.
❗ 어려웠던, 곤란했던
1. 다시 색칠할 필요가 있는지 검사
위에서 언급한 문제이다. 배열에 다음 부분과 현재 부분을 검사하는 것이 정답이라 생각하였는데, 문제에 대해 깊게 생각하지 못하였던 부분이 문제였따.
2. 반복문 구성
해당 문제를 해결하기 위해서 반복문 4개를 사용하였다. 단순한 배열 탐색 같은 경우할 수 있으나, 조금이라도 꼬아버린 문제를 만나면 배열 문제에서 나 스스로가 굉장히 약하다는 것을 느낀다. 이번 문제를 풀면서도 어떻게 해야 반복문을 잘 구성해서 88보다 큰 보드도 88씩만 비교할 수 있을지 고민을 많이 하였다. 여러모로 문제를 많이 풀어보고 접할 필요가 있다고 강하게 생각하게 되었다
🧾 전체 코드
# 1. 체스판 입력
N, M = map(int, input().split())
board = []
repaint_list = []
for _ in range(N):
board.append(input())
# 2. 체스판 경우의 수 모두 탐색
# 8*8 보다 크다면 칸을 이동하며 8*8 크기에서 탐색
for i in range(0, N - 7):
for j in range(0, M - 7):
# 체스판의 시작이 흰색일수도, 검정일수도..
start_white = 0
start_black = 0
# 8*8 크기로 탐색 진행
for k in range(i, i+8):
for m in range(j, j+8):
if (k+m) % 2 == 0:
if board[k][m] != 'W':
start_white += 1
if board[k][m] != 'B':
start_black += 1
else:
if board[k][m] != 'B':
start_white += 1
if board[k][m] != 'W':
start_black += 1
repaint_list.append(min(start_white, start_black))
print(min(repaint_list))
