[Python] 백준 파이썬 1018 체스판 다시 칠하기

https://www.acmicpc.net/problem/1018

1018번: 체스판 다시 칠하기

• 첫 시도

# 백준 1018 체스판 다시 칠하기
m, n = map(int, input().split())

plate = []
for _ in range(m):
  plate.append(list(input()))

need_draw_square=[]

for i in range(m-7):
  for j in range(n-7):
    cnt = 0 # 몇 번 색칠하는지
    for w in range(8):
      for v in range(7):
        if plate[i+w][j+v] != plate[i+w][j+v+1]:
          pass
        elif plate[i+w][j+v] == plate[i+w][j+v+1]:
          if plate[i+w][j+v] == 'W':
            plate[i+w][j+v+1] = 'B'
            cnt += 1
          elif plate[i+w][j+v] == 'B':
            plate[i+w][j+v+1] = 'W'
            cnt += 1
    need_draw_square.append(cnt)

print(need_draw_square)

처음 문제를 접했을 때 '다시 칠해야 하는 정사각형의 최솟값'의 의미가 와닿지가 않았습니다.

그래서 일단 행, 열을 전부 돌아다니면서 자기 앞에 있는 색과 다르면 바꾸는 식으로 해줬는데, 출력에서 보시다시피 문제와는 전혀 맞지 않는.... 결과가 나왔습니다.. ㅎㅎ

 

제가 생각한 문제점은

1. 실제로 행렬 값을 바꾸는 방식으로 진행하면 안 된다. 
2. 같은 행에서 이웃하는 색이 같은 애들은 다 바꿨지만 이웃하는 행에 대해서는 고려를 안 해줬다.

이 두 가지입니다.

 

슬프게도 이번엔 다른 분들의 도움을 받기로 했습니다...😢

 

• 다른 분의 풀이

m, n = map(int, input().split())
plate = []
count = []

for _ in range(m):
    plate.append(input())

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

print(min(count))

이 풀이와 저의 풀이의 차이점을 보면

1. 첫 시작이 흰색일 때, 검은색일 때의 두 가지 경우로 생각해줌
2. 값을 실제로 바꾸는 것이 아니라 횟수만 체크
3. 행과 열의 인덱스가 짝수일 때와 홀수일 때의 경우를 체크

풀이를 보고 행열의 인덱스로 첫 시작과의 관계를 생각할 수 있구나! 하는 걸 알았습니다...

0, 0	0, 1	0, 2
1, 0	1, 1	1, 2
2, 0	2, 1	2, 2

이런 행렬이 있다고 하겠습니다. 각 숫자는 (행 인덱스, 열 인덱스)입니다.

각 값의 합을 보면

0 (짝)	1 (홀)	2 (짝)
1 (홀)	2 (짝)	3 (홀)
2 (짝)	3 (홀)	4 (짝)

이처럼 인덱스의 합으로 첫 시작과 색이 같아지는 부분을 찾을 수 있습니다.

 

문제가 어려워서 한 번에 풀지는 못했지만 그래도 새로운 방법을 하나 알게 되어 좋았습니다 ^_^