[백준 알고리즘/python] 백준 1018번 체스판 다시 칠하기, 파이썬 설명

백준 알고리즘의 브루트 포스 단계, 1018번 체스판 다시 칠하기를 파이썬으로 풀어보았다.

문제 출처

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

1018번: 체스판 다시 칠하기

 

이 문제는 난이도가 조금 있었다.

문제 해석 먼저 하자면

 

#1. 크기가 N*M이고, 흰색과 검은색으로 막 칠해져있는 보드판이 있다.

#2. 이 보드판을 잘라서 8*8크기의 체스판으로 만들려고 한다.

#3. 체스판은 흰색과 검은색이 번갈아가며 체크무늬를 이루어야 한다.

#4. 보드판을 잘라서, 체스판을 만들기 위해서 알맞게 색을 고쳐서 체크무늬를 만들어야 한다.

#5. 고쳐야 하는 색의 최소값을 구하라.

 

대충 이정도이다.

문제에 힌트가 한줄 적혀있는데, "정의대로라면 체스판의 시작이 흰색이거나, 검은색이거나 둘 중 하나이다." 라는 구문이다.

 

 

이 문제는 브루트포스 문제이다.

브루트포스는 모든 경우의 수를 다 돌려서, 최적의 해를 구하는 방식이다.

그렇다면 이 문제에서 모든 경우의 수를 다 돌리려면 어떻게 해야할까?

 

생각 

#1. 먼저 N*M만큼의 보드를 받아온다.

#2. 8*8로 잘라야 하기에, 행으로 i-7만큼, 열로 j-7만큼 고정시켜 줘야 한다. 이 방법이 아니고서는 인덱스 에러를 잡을 방법을 모르겠다.

#3. 고정시키고 난 이후는, i,j에서 i+8까지, j+8까지 전부 반복하면서 알맞게 체크무늬로 칠해져 있는지 확인한다.

#4. 흰색이 먼저인 경우와 검은색이 먼저있는 경우를 나누어서, 한번에 종합한 후, min()을 사용하여, 최소값을 알아낸다.

 

이정도로 생각하고 코드를 썼다.

 

 

N, M = map(int, input().split())
board = list()
for i in range(N):
    board.append(input())
repair = list()

 입력값들을 받아오는 코드이다.

 

for i in range(N-7):
    for j in range(M-7):
        first_W = 0
        first_B = 0
        for k in range(i,i+8):
            for l in range(j,j + 8):
                if (k + l) % 2 == 0:
                    if board[k][l] != 'W':
                        first_W = first_W+1
                    if board[k][l] != 'B':
                        first_B = first_B + 1
                else:
                    if board[k][l] != 'B':
                        first_W = first_W+1
                    if board[k][l] != 'W':
                        first_B = first_B + 1
        repair.append(first_W)
        repair.append(first_B)

 이렇게 4중 for문을 사용했다.

먼저, i와 j로 8*8의 최대 크기를 조절해 준다.

왜냐하면, 9*9 보드에서 자를 수 있는 경우의 수는, 2*2로 4가지이다.

또, 10*10 보드에서 자를 수 있는 경우의 수는 3*3으로 9가지이다.

즉, N*M 보드에서 자를 수 있는 경우의 수는 N-i * M-j 가지가 된다.

 

이후에 흰색으로 시작한 경우, 검은색으로 시작한 경우의 값을 초기화 해 준 뒤,

k와 l을 통해서 처음 자른 체스판부터 검사를 시작한다. 여기서, 조건문을 보면, 

( k + l ) %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

체스판 색의 인덱스(k,j)

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

체스판 색 인덱스의 합( k +j )

 

위와 같이, 인덱스의 합이 짝수인지 홀수인지로 체크무늬를 판단 할 수 있다.

 

전체 코드 in 깃허브