백준 1018번 체스판 다시 칠하기 파이썬 풀이

[Python] 백준 알고리즘 온라인 저지 1018번 체스판 다시 칠하기

1018 체스판 다시 칠하기

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

1018번: 체스판 다시 칠하기

처음에는 문제를 잘못 이해하여 쉬운 문제라고 생각하고 풀었다가 좌절을 맛봤다. 다른 분들의 풀이를 참고하여 풀 수 있었다.

이 문제에서도 브루트 포스를 사용하고 8x8 크기의 체스판을 모두 비교하여 가장 적은 칸을 칠하는 값을 구하는 문제이다.

---

코드

n, m = map(int, input().split())
chess =[list(input()) for _ in range(n)] # chess라는 변수에 보드값을 리스트로 저장
cnt = []
#시작점 8x8 크기의 보드를 만들 수 있는 모든 경우 계산하는 for문
for i in range(n - 7):
    for j in range(m - 7):
        w_cnt, b_cnt = 0, 0
        for k in range(i, i+8): #시작점을 기준으로 8칸씩 모두 체크
            for l in range(j, j+8):
                if (k+l) % 2 == 0: #현재행의 번호 k,l의 합이 짝수이면 시작점과 색 같아야함
                    if chess[k][l] != 'W': #화이트 먼저 시작인 보드
                        w_cnt += 1
                    if chess[k][l] != 'B': #블랙이 먼저 시작인 보드
                        b_cnt += 1
                else:   #현재행의 번호 k,l의 합이 홀수이면 시작점과 색이 달라야함
                    if chess[k][l] != 'B':
                        w_cnt += 1
                    if chess[k][l] != 'W':
                        b_cnt += 1
        cnt.append(w_cnt) #두개의 수를 cnt에 넣고 작은값 출력
        cnt.append(b_cnt)
print(min(cnt))

---

풀이

브루트 포스를 이용하여 가능한 모든 경우를 계산하는 문제로 어떤 분은 아예 맞는 체스 보드 두 가지를 리스트로 만들어 놓고 비교하여 계산하는 경우도 있었다. 

우선 입력값 n, m을 받고 n 만큼의 길이의 입력값을 리스트로 chess라는 변수에 저장한다.

그리고 가장 작은 값을 비교하기 위해 빈 리스트 cnt를 선언하고 for문으로 8x8의 보드를 만들 수 있는 시작점을 모두 찾는다 즉 n-7은 n이 13일 때 6가지 시작점이 나온다(첫 번째 칸부터 6번째 칸까지) 그다음 for문으로 y축의 경우도 모두 구한다.

이후에는 시작점을 기준으로 x, y 모두 8칸씩 비교한다. 홀수와 짝수의 경우가 다르기 때문에 이를 이용하여 조건문을 작성한다. 현재 행과 열 k, l의 합이 짝수이면 시작점과 색이 같아야하고 홀수라면 달라야 한다. 또한 짝수일 때 w로 시작한 보드와 b로 시작한 보드 두 가지 경우를 모두 계산하여(w_cnt, b_cnt)를 cnt 리스트에 넣고 둘 중 더 작은 값을 출력하는 것으로 마무리한다.

---

풀이 결과

풀이 결과