[Python]백준 #1018 체스판 다시 칠하기

✔️알고리즘

• 브루트포스

 

✔️접근방법

1. 주어진 체스판의 모든 8x8 형태의 부분집합 경우의 수를 다 검사한다.

2. 8x8 체스판은 BWBWBWBW 이나 WBWBWBWB가 반복되면서 이루어져 있다. 어떤 배열이 먼저 시작하는 것이 효율적인지는 알 수 없기 때문에 각각의 경우를 모두 검사한다.

 

mini=64 #8x8 체스판 모두 바꾸는 경우가 최대
str1 = 'BWBWBWBWWBWBWBWBBWBWBWBWWBWBWBWBBWBWBWBWWBWBWBWBBWBWBWBWWBWBWBWB'
str2 = 'WBWBWBWBBWBWBWBWWBWBWBWBBWBWBWBWWBWBWBWBBWBWBWBWWBWBWBWBBWBWBWBW'

def compare_str(chass, str):
    global mini #전역변수 사용 위해 global 선언
    count=0
    #8번씩 문자 8개 비교
    for i in range(64):
        if(chass[i]!=str[i]):
            count = count+1
    if(count < mini):
        mini = count

#보드 생성
borad=[]
while(1):
    N, M = map(int,input().split(" "))
    if(N<0 |N<8 | M>50):
        print("N, M은 8이상 50이하")
        break
    else:
        for i in range(N):
            borad.append(input())
        break
print(borad)

for i in range(N-7):
    for j in range(M-7):
        chass=''
        for k in range(8):
            chass = chass+borad[i:i+8][k][j:j+8]
        #print(chass)
        compare_str(chass, str1)  # 8x8 부분 집합
        compare_str(chass, str2)
           
print(mini)

 

✔️배운점/아쉬운점

1. 처음엔 B, W의 갯수가 각 32개가 되면 해결된다고 생각했는데 B,W가 연속적으로 나오면서 32개가 될 수도 있기 때문에 틀린 접근방식이었고 시간을 많이 잡아먹었다. 

2. 브루트포스 알고리즘은 말 그대로 하나하나 다 해보는 알고리즘인데 설마? 하는 마음에 자꾸 뭔가 더 간단한 방법을 찾으려다가 가장 쉬운 알고리즘을 못 찾고 헤매는 것 같다.

3. 0보다 작을 때 예외 처리를 안 해주면 런타임에러(IndexError)가 난다.