1018 체스판 다시 칠하기 (백준 S5)

이 문제를 오래 잡아두고 있었지만 결국 못풀고서 다른분들 풀이를 보고서 이해한 내용을 정리해보려한다.

문제 내용은 아래와 같다

• 크기는 N * M 이고, 마구잡이로 W,B로 채워져있다
• 이 보드판을 잘라서 8*8크기의 체스판(W,B가 순서대로 그려져있는)으로 만들려고 한다.
• N M 보드판 중 W나 B를 적게 수정하는 부분을 골라서 몇 번 고치는 8 8 영역을 파악한다.
• 파악한 8 * 8 영역에서 W,B를 수정한 갯수를 출력한다

일단 입력을 받고 받은 문자들을 저장

N, M = map(int, input().split())

count = []

original = [list(input()[:M]) for _ in range(N)]

나는 2차원 배열로 만들었는데, 굳이 2차원 배열로 만들어주지 않아도 된다((문자열로 저장해도 인덱스에 접근할 수 있기 때문))

모든 8 * 8의 경우의 수를 순회하기 위해

for a in range(N-7):
  for b in range(M-7):
    first_White = 0
    first_Black = 0

체스판 공간을 뺀 영역만큼 for 문을 돌려준다

first_White , first_Black 은 처음에 시작하는 단어에 따라서 달라지는 W,B가 수정되는 갯수를 모두 카운팅하기 위함

위에 가져온 경우의 수 행과 열 시작점(a,b)을 기준으로 8칸을 탐색

    for i in range(a,a+8):
      for j in range(b,b+8):

행과 열의 번호의 따라 생기는 규칙을 가지고 카운팅

        if (i + j) % 2 == 0:
          if original[i][j] != 'W':
            first_White += 1
          if original[i][j] != 'B':
            first_Black += 1
        else:
          if original[i][j] != 'B':
            first_White += 1
          if original[i][j] != 'W':
            first_Black += 1

사진과 같이 B,W 가 체스판처럼 놓이는 규칙이 존재한다, 행과 열의 인덱스 번호의 합이 홀수와 짝수인 경우에 따라 일정한 색을 가진다, 이것을 가지고서 B,W중 어떤 것이 놓일지 판단할 수 있다

전체코드

N, M = map(int, input().split())

count = []

original = [list(input()[:M]) for _ in range(N)]


for a in range(N-7):
  for b in range(M-7):
    first_White = 0
    first_Black = 0
    for i in range(a,a+8):
      for j in range(b,b+8):
        if (i + j) % 2 == 0:
          if original[i][j] != 'W':
            first_White += 1
          if original[i][j] != 'B':
            first_Black += 1
        else:
          if original[i][j] != 'B':
            first_White += 1
          if original[i][j] != 'W':
            first_Black += 1
    count.append(min(first_White,first_Black))

print(min(count))