체스판 다시 칠하기 - 1018

 

문제를 보고 8x8 체스판으로 잘라낸 후 에 몇개의 정사각형을 다시 칠해야하겠다고 생각하는지 계산

여기서 왼쪽위(즉 시작위치가) 흰, 검 중 1개 이다.

 

import sys
input = sys.stdin.readline
chess1=[['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']]
chess2=[['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']]

N,M = map(int,input().split())
data = []
for i in range(N):
  data.append(list(input().strip()))
min_count = float('inf')
for i in range(N-7):
  for j in range(M-7):
    check1 = 0
    check2 = 0
    for k in range(8):
      for l in range(8):
        # print(chess1[k][l],data[i+k][j+l])
        if chess1[k][l] != data[i+k][j+l]:
          check1 += 1
        if chess2[k][l] != data[i+k][j+l]:
          check2 +=1
    min_count = min(min_count, check1, check2)

    
print(min_count)

미리 답지를 적해놓고 비교하는 방법을 선택했다.

아래 코드는 최적화 코드라며 작성해준 코드이다.

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
data = [list(input().strip()) for _ in range(N)]

# 최소 변경 횟수 저장
min_count = float('inf')

for i in range(N - 7):
    for j in range(M - 7):
        check1, check2 = 0, 0  # W로 시작하는 경우와 B로 시작하는 경우

        for k in range(8):
            for l in range(8):
                # (i + k, j + l) 위치에서 (i, j)에서 시작하는 체스판 패턴과 비교
                if (k + l) % 2 == 0:  # 시작 색과 동일해야 하는 위치
                    if data[i + k][j + l] != 'W':  
                        check1 += 1  # 'W' 시작일 때 다시 칠해야 함
                    if data[i + k][j + l] != 'B':
                        check2 += 1  # 'B' 시작일 때 다시 칠해야 함
                else:  # 시작 색과 반대여야 하는 위치
                    if data[i + k][j + l] != 'B':
                        check1 += 1  # 'W' 시작일 때 다시 칠해야 함
                    if data[i + k][j + l] != 'W':
                        check2 += 1  # 'B' 시작일 때 다시 칠해야 함
        
        # 현재 8x8 영역에서 최소 변경 횟수 갱신
        min_count = min(min_count, check1, check2)

print(min_count)

 

백준 기준으로 속도 비교를 해봤다.

그렇다.