문제
지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다.
체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.
보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8×8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8*8 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.
링크 참조
풀이 설명
체스판은 두 가지 모드로 칠해져야 한다.
1. 검은색이 먼저 칠해지던가
2. 흰색이 먼저 칠해지던가
4 x 4 의 크기라고 생각하면 이런식으로 채워져야 한다.
입력 받은 크기의 큰 체스판에서 8 x 8만큼의 체스판을 규칙에 맞게 그리려면
지민이는 해당 구역에서 체스판을 다시 그려야 한다.
그 그릴 구역이 가장 작을 수 있는 경우를 출력 하면 된다.
코드
import sys
N, M = map(int,input().split())
A = [[]*M for _ in range(N)]
#A 배열 안에 보드의 상태가 담겨 있음
for i in range(N):
A[i] = list(input())
#모드1: B으로 시작되는 곳에서 시작
#모드2: W으로 시작되는 곳에서 시작
mode1 = ['B','W','B','W','B','W','B','W']
mode2 = ['W','B','W','B','W','B','W','B']
startidx = 0
endidx = 8
startarr = 0
endarr = 7
ans = []
while endarr < N:
answer1 = 0
answer2 = 0
#case 1: 블랙부터 시작
for i in range(startarr, endarr+1):
new = A[i][startidx:endidx]
if i % 2 == 0:
if new == mode1:
answer1 += 0
else:
for i in range(8):
if mode1[i] != new[i]:
answer1 += 1
else:
if new == mode2:
answer1 += 0
else:
for i in range(8):
if mode2[i] != new[i]:
answer1 += 1
#case 2: white부터 시작
for i in range(startarr, endarr+1):
new = A[i][startidx:endidx]
if i % 2 == 0: #짝수행
if new == mode2:
answer2 += 0
else:
for i in range(8):
if mode2[i] != new[i]:
answer2 += 1
else: #홀수행
if new == mode1:
answer2 += 0
else:
for i in range(8):
if mode1[i] != new[i]:
answer2 += 1
startidx += 1
endidx += 1
if endidx > M:
startidx = 0
endidx = 8
startarr += 1
endarr += 1
ans.append(answer1)
ans.append(answer2)
print(min(ans))A 라는 이차원 리스트를 만들어 입력 받은 M X N 의 체스판을 담았다.
그리고 8 X 8 크기로 무조건 잘라낼 것이기 때문에
원하는 패턴이 그려져있는 mode 리스트 2개를 만들었다.
하나는, B 이 먼저 시작하는 버전
다른 것은 W 가 먼저 시작하는 버전이다.
0번째 행을 B으로 시작하는 모드라면
1번째 행은 W로 시작하는 모드여야 한다.
따라서, 나는 마지막 열이 입력 받은 크기보다 작을 때까지로 while문을 만들었다.
이후, 해당 행의 8개를 슬라이스 하여 담아낸 new 배열을
mode1 / 2 리스트와 비교했다.
짝수행들끼리는 같은 모드로 비교하고, 홀수행들끼리는 다른 모드로 비교해야 한다.
이런식으로 만들 수 있는 모드는 2개이기에, answer1/2로 나누어 총 ans 리스트에 담았다.
실제로 ans 배열을 출력해보면, 원래의 배열에서 8 X 8 로 자를 수 있는 경우의 수만큼 원소가 있는 것을 볼 수 있다.
그 중에서 문제는 가장 적게 바꿀 수 있는 경우를 물었음으로,
min(ans) 으로 출력하였다.
💌
끝으로
이 문제는 이해하기는 쉬웠다.
하지만 slice와 for문 범위에 쓰여지는 변수가 4개나 되었던 것 떄문에
하나의 예제에서 계속 통과가 되지 않았던 어려움이 있었다.
이는 slice범위와 관련된 index 범위 지정에서 있던 것에서 오류를 발견하였다.
시간복잡도를 줄이고 싶은 생각을 많이 했는데, 배열을 통으로 비교하지 않고 하나하나당 검사하는 것 말고는 다른 아이디어가 떠오르지 않고 있다 😅
