[Python] BOJ 1018 체스판 다시 칠하기

1. 요구사항

• 시간 제한: 2초
• 메모리제한: 128MB
• 보드 안에서 시작 가능한 모든 8x8 시작 위치를 고르고
• w로 시작 체스판과 비교했을 때, 다시 칠해야 하는 칸 수
• b로 시작 체스판과 비교했을 때, 다시 칠해야 하는 칸 수
• 둘 다 계산해서 더 작은 값만 취함. 

2. 설계

• N, M 을 입력 받는다.
• board 를 입력 받아 초기화한다.
• answer = 64
  • 최대로 다시 칠해야 하는 경우의 수는 64번이다. 
• • 최대 8x8 이니
  • 시작점 i, j의 범위는 (N - 7) (M - 7) 
  • - 7 인 이유 
    • 시작인덱스는 0 ~ 전체길이 -8 까지 가능
    • 0을 포함해야 하기 때문에 -7
  • cnt_w = 0, cnt_b = 0
    • 시작점마다 w, b 각각 칠해야하는 경우의 수를 카운트한다.
  • 이제 각 시작점 마다 돌아야한다.
  • 현재 위치 r, c 의 범위는 (i, i +8) 과 (j, j + 8):
  • 시작점으로부터 끝까지 순회하면서, 짝수와 홀수인 경우를 생각한다.
  •  
  • 짝수인 경우 무조건 시작점과 색깔이 같아야 한다. 
    • if 현재 위치 != 'W':  # 시작점이 w든 b든 같다. 헷갈리면 시작점이 W라고 생각하면 된다.  그럼 시작점과 색이 다르니 W칠해줘야지
      • cnt_w += 1
    • if 현재 위치 != 'B':
      • cnt_b += 1
  • 홀수인 경우 무조건 시작점과 색깔이 달라야 한다. 시작 가능한 위치를 고른다. 
    • else:
      • if 현재 위치 != 'W':  #이 때도 시작점이 W이면 홀수는 B여야한다. 
        • cnt_b += 1:
      • if 현재위치 != 'B':
        • cnt_w += 1

시작점과 현재위치가 짝수면 같고 홀수면 다름을 시각적으로 보여주는 자료

• answer = min(answer, cnt_w, cnt+b) 하여 최소 칠해야 되는 경우의 수를 찾는다. 

3. 구현

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

answer = 64 # 최대 다시 칠해야 하는 경우의 수느 64를 넘길 수 없다.

# i, j 는 8x8 체스판이 시작 가능한 위치
for i in range(N-7):
    for j in range(M-7):
        # 시작점에서 0으로 초기화
        cnt_w, cnt_b= 0, 0
        for r in range(i, i+8):
            for c in range(j, j+8):
                cur = board[r][c]
                if (r + c) % 2 == 0: # 짝수, 시작점과 같아야 함.
                    if cur != 'W':
                        cnt_w += 1
                    if cur != 'B':
                        cnt_b += 1
                else: # 홀수, 시작점과 달라야함
                    if cur != 'W':
                        cnt_b += 1
                    if cur != 'B':
                        cnt_w += 1
        answer = min(answer, cnt_b, cnt_w) # 각 시작점마다 칠해야 되는 최소 개수를 구함.

print(answer)

4. 생각해볼 문제

1. 다중 for문 시간제한 2초 괜찮았을 까? 

여기서 N, M 은 최대 8 ~ 50이다. 

시작점 마다 64번 검사

64 * (N - 7) * (M - 7) 

64는 상수 -7도 상수 이므로

대략적으로 O(NM) 이다. N,M이 최대일 때, 시간 복잡도는 O(N^2) 이 된다. 

 

실제 연산횟수를 구하면 

64 * (50 -7) * (50 -7) = 118,336번 으로 여유있다.