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

문제

나의 답안

n,m=map(int,input().split())

mtr=[]
cnt=[]
for i in range(n):
    mtr.append(input())
    
for a in range(n-7):
    for b in range(m-7):#8*8로 자르기 위해, -7해준다
        w_index=0 #흰색으로 시작
        b_index=0 #검은색으로 시작
        for i in range(a,a+8):#시작지점
            for j in range(b,b+8):#시작지점
                if (i+j)%2==0:#짝수인 경우
                    if mtr[i][j]!='W':#W가 아니면, 즉 B이면
                        w_index+=1#W로 칠하는 갯수
                    else:#W일 때
                        b_index+=1#B로 칠하는 갯수
                else:#홀수인 경우
                    if mtr[i][j]!='W':#W가 아니면, 즉 B이면
                        b_index+=1#B로 칠하는 갯수
                    else:
                        w_index+=1#W로 칠하는 갯수
                        
        cnt.append(w_index) #W로 시작할 때 경우의 수
        cnt.append(b_index) #B로 시작할 때 경우의 수
print(min(cnt))

접근 방법

• 다시 칠해야 하는 경우
  • 하나는 맨 왼쪽 위 칸이 흰색인 경우
  • 하나는 검은색인 경우
• 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다
• 문제 조건에 따라, 8×8 크기의 체스판으로 잘라내야 함
• 행과 열의 인덱스의 합계가 짝수면 처음 색과 같아야, 홀수면 달라야한다.
  • 예를들어

i,j	i,j	i,j	i,j
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

와 같은 배열을 이루고 있다고 하면
아래와 같이 합이 홀수인 경우는
처음과 다른 색을 이루고 있어야 서로 다른 색의 배열을 가질 수 있다.

i,j	i,j	i,j	i,j
0 (W)	1 (B)	2 (W)	3 (B)
1 (B)	2 (W)	3 (B)	4 (W)
2 (W)	3 (B)	4 (W)	5 (B)
3 (B)	4 (W)	5 (B)	6 (W)

1. n과 m을 입력받고, 문자열을 저장할 mtr 배열과 다시 칠해야 하는 정사각형 개수를 저장할 cnt 배열을 선언한다.

2. 반복문으로 체스판을 색칠한다.

3. 체스판을 8*8으로 잘라주어야 하기에

   for a in range(n-7):
       for b in range(m-7): 

   와 같이 반복문을 돌려준다.

4. 체스판이 무슨 색으로 시작하는지 판별하기 위해 w_index와 b_index 변수를 0으로 초기화 해준다.

5. 행과 열의 시작지점을 파악하기 위해 다음과 같은 반복문을 돌려준다.

   for i in range(a,a+8):#시작지점
               for j in range(b,b+8):#시작지점 

6. 이후 짝수인 경우, 각 값이 W인지 아닌지에 따라 w_index와 b_index 변수를 증가시켜 준다.
   짝수인 경우(첫번째 값과 같아야 함)

   • 6-1. 해당 값이 B이면 W로 칠해야 하므로, w_index을 1증가시켜 준다.
   • 6-2. 해당 값이 W이면 B로 칠해야 하므로, b_index을 1증가시켜 준다.

7. 마찬가지로 홀수인 경우, 각 값이 W인지 아닌지에 따라 w_index와 b_index 변수를 증가시켜 준다.
   홀수인 경우(첫번째 값과 달라야 함)

   • 7-1. 해당 값이 B이면 B로 칠해야 하므로, b_index을 1증가시켜 준다.
   • 7-2. 해당 값이 W이면 W로 칠해야 하므로, w_index을 1증가시켜 준다.

8. 각 문자열의 시작지점에 대한 모든 반복문을 종료한 후 cnt 배열에 w_index와 b_index를 추가한다.

9. 이후 min을 사용해 다시 칠해야 하는 정사각형의 최소 개수를 출력해준다.

이게 실버 5문제라고..? 싶었던 문제이다... 나중에 다시 풀어봐야지