백준 1018 체스판 다시 칠하기

문제

---

솔루션

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

for _ in range(n):
    li.append(input())
cnt=[]

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

---

깨달은 점

브루트 포스(brute force)
brute: 무식한, force: 힘,   무식한 힘으로 완전탐색 알고리즘
가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만을 가져옴

이 문제는 브루트 포스 알고리즘을 사용해야한다.

 

체스판 크기도 잘라서 해야하고 B/W 확인도 해야해서 복잡하게 생각했다.

처음에는 B,W 형식의 리스트를 두개 만들어서 해야하나 했지만

모든 경우의 수 돌면서 비교해서 해야했다.

 

for i in range(n-7):
    for j in range(m-7):

이 부분은 행과 열의 시작 고정 부분이고,

 

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

이 부분으로 8X8 의 모든 행과열을 돈다.

 

                if (a+b) % 2 ==0 :
                    if li[a][b]!='W':
                        B+=1
                    if li[a][b] !='B':
                        W+=1
                else:
                    if li[a][b] !='B':
                        B+=1
                    if li[a][b] !='W':
                        W+=1

칸이 짝수번째인지, 홀수번째인지( 흰색이 먼저인 경우와 검은색이 먼저있는 경우 ) 를 나누어 

매칭이 되지 않는 부분을 세어준다

 

**if (a+b) % 2 ==0를 하는이유

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

체스판 색의 인덱스(a,b)

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

행과 열의 인덱스의 합을 이용해

홀짝을 구분하면 색깔이 같은 경우라는 것을 알 수 있다. 

 

        cnt.append(B)
        cnt.append(W)
        
print(min(cnt))

min()을 사용하여 최소값을 구한다.