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

solved.ac 난이도 : silver5

백준 1018번- 파이썬 풀이

 

<문제>

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

1018번: 체스판 다시 칠하기

<풀이>-완전탐색(브루트포스 알고리즘)

체스판이 W로 시작하는 경우 체스판이 B로 시작하는 경우로 나눈다.

각각의 경우에서 새로 칠해야하는 체스판의 갯수를 구한다.

index1 : w로 시작하는 경우 새로 칠해야하는 체스판의 갯수

index2 : B로 시작하는 경우 새로 칠해야하는 체스판의 갯수

i : 행의 인덱스

j : 열의 인덱스

(i+j)%2 = 0(i+j가 짝수인 경우) : 시작점의 색깔과 같아야한다.

(i+j)%2=1(i+j)가 홀수인 경우) : 시작점의 색깔과 달라야한다.

 

8*8행렬로 자르기

for a in range(n-7):
    for b in range(m-7):
        index1 = 0 #w로 시작할 경우
        index2 = 0 #B로 시작할 경우
        for i in range(a,a+8):
            for j in range(b,b+8):

a : 0부터 n-8까지 반복

b : 0부터 m-8까지 반복

a,b : 8*8행렬로 자를 경우 시작점의 위치

i,j :  a,b부터 8*8행렬의 길이만큼 반복하는 인덱스

<코드>-파이썬

from collections import deque
n,m = map(int,input().split())
info = []
count = []
for _ in range(n):
    info.append(list(input()))
for a in range(n-7):
    for b in range(m-7):
        index1 = 0 #w로 시작할 경우
        index2 = 0 #B로 시작할 경우
        for i in range(a,a+8):
            for j in range(b,b+8):
                if (i+j)%2 == 0: #합이 짝수인 경우 -> 시작점의 색깔과 같아야한다.
                    if info[i][j]!='W':
                        index1+=1
                    if info[i][j]!='B':
                        index2+=1
                else: #합이 홀수인 경우 -> 시작점의 색깔과 달라야한다.
                    if info[i][j] == 'W':
                        index1+=1
                    if info[i][j] == 'B':
                        index2+=1
        count.append(min(index1,index2))
print(min(count))

a,b의 시작점의 위치 각각에서 index1과 index2의 값 중 작은값을 count에 추가한다.

반복문이 끝난 후 count배열에서 최솟값을 출력한다.