[baekjoon] 1018번 : 체스판 다시 칠하기 by pyhton

 

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

1018번: 체스판 다시 칠하기

code

N , M = map(int,input().split()) #N:세로 M:가로
board = []
count = []
for _ in range(N):
    board.append(input())

for i in range(N-7):
    for j in range(M-7):
        f_w = 0
        f_b = 0
        for x in range(i,i+8):
            for y in range(j,j+8):
                if (x+y)%2 == 0: #x+y 합이 짝수라면 일정한색을 가짐
                    if board[x][y] !="W":
                        f_w += 1
                    if board[x][y] != "B":
                        f_b += 1
                else:       # 합이 홀수여도 일정한색을 가짐
                    if board[x][y] != "B":
                        f_w += 1
                    if board[x][y] != "W":
                        f_b += 1

        count.append(f_w)
        count.append(f_b)

print(min(count))

이번문제는 브루트포스를 사용하는 문제였는데 해결 방법을 찾는데 상당히 어려웠다.

 

우선 8x8로 잘라내긴 했는데, 어떻게 탐색을 해야할지 감이 오지 않았다.

 

 

https://god-gil.tistory.com/62

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

위에 블로그에서 사용하는 탐색법이 가장 좋아보여 사용하게 되었다.

 

내용의 핵심은

인덱스의 행과 열의 합이 짝수일 경우 일정한 색을 가지고

그 반대의 경우도 마찬가지로 일정한 색을 가진다는 것이다.

 

제일 중요한 포인트는 

핵심을 이용하여 나눈 체스판을 흰색으로 시작할것인지 

검정으로 시작할것인지 나누어 계산하면 된다.

>>이 부분에서 상당히 헷갈려 했음으로 하나 하나 자세히 기록하였다.

 

 

기본적인 입력은 아래와 같이 하였다.

N , M = map(int,input().split()) #N:세로 M:가로
board = []
count = []
for _ in range(N):
    board.append(input())

여기서 board는 입력한 체스판의 색깔을 포함하고있고

count는 변환해야되는 색의 갯수를 저장해 추후 min함수를 통해 최소로 변환해야되는 색의 수를 한번에 알아내기 위해 선언한다.

 

 

 

8×8 크기의 체스판으로 잘라내기 위해

for i in range(N-7):
    for j in range(M-7):
        f_w = 0
        f_b = 0
        for x in range(i,i+8):
            for y in range(j,j+8):

위와같이 4중 for문을 사용하여 입력받은 (N,M)을 시작으로 8x8크기를 잘라 탐색하는데 

인덱스에러를 피하기 위해 N과 M에 -7을 하여 인덱스 값을 벗어나지 않게 탐색한다.

 

 

 

이제 8x8크기로 잘린 체스판에서 탐색을 하는데

이 문제의 핵심이였던 행과 열의 인덱스 합이 짝수일 경우 일정한 색을 가지는것을 이용해 

합이 짝수인경우 or 합이 홀수인경우를 나누어 카운트 해주면된다.

                if (x+y)%2 == 0: #x+y 합이 짝수라면 일정한색을 가짐
                    if board[x][y] !="W":
                        f_w += 1
                    if board[x][y] != "B":
                        f_b += 1
                else:       # 합이 홀수여도 일정한색을 가짐
                    if board[x][y] != "B":
                        f_w += 1
                    if board[x][y] != "W":
                        f_b += 1

만약 합이 짝수인 경우에서 흰색으로 시작하였다면 

합이 홀수인 경우에서는 검정이 되야한다.

 

f_w는 체스판 처음이 white로 시작할경우 ,

f_b는 체스판 처음이 black으로 시작할경우 이다

 

 

예를 들면 첫줄 입력이 아래와 같다고 치자

>>WBWBWBWB

첫번째값의 행과 열의 인덱스 합이 짝수임으로 큰 if문으로 들어간다.

값은 White임으로 f_w는 그대로 f_b는 증가한다.

이유는 f_w는 체스판이 흰색으로 시작할 경우임으로 

행과 열의 인덱스 합이 짝수 인경우는 흰색이여야 하는데 이에 만족하여 페인트를 칠할 필요가 없어서 이고,

f_b가 증가하는 이유는 f_b는 검정체스판으로 시작할 경우임으로 

행과 열의 인덱스 합이 짝수인 경우에 검정이여야 하는데 해당 값이 흰색임으로 페인트를 칠해야 하여 값을 증가시킨다.

 

 

두번째 값의 행과 열의 인덱스 합이 홀수 임으로 큰 else 문으로 들어간다.

값은 Black임으로 f_w는 그대로 f_b는 증가한다.

이유는 f_w일때에는 흰색으로 시작한 체스판이기에 행과 열의 인덱스 합이 홀수일때에는 검정이 되야하기때문에

f_w의 값은 증가 시킬 필요가 없고

f_b일때는 검정으로 시작한 체스판이기에 행과열의 인덱스의 합이 짝수일때 검정이되고 홀수일때 흰색이기에,

f_b의 값을 증가시킨다음 색을 칠해 주어야 한다.

 

 

 

위와같이 자른 체스판 하나를 모두 탐색하여

흰색으로 시작하는 경우 f_w 에 색칠해야하는 경우와

검정으로 시작하는 경우 f_b 에 색칠해야하는 경우를

append를 이용하여 count 리스트에 추가해준다

        count.append(f_w)
        count.append(f_b)

 

 

자를 수 있는 체스판을 모두 탐색한뒤에는 

min 함수를 이용하여 count 리스트에 저장된 경우의 수중 가장 최소값을 출력해주면 된다.

print(min(count))

 

 

 

아무래도 말로 설명하려다 보니 되게 힘든데  해결하는 과정중 이 부분에서 상당히 머리속에서 꼬였던만큼 더 자세히 풀게 되었다. 앞으로 비슷한 유형이 있다면 더 쉽게 풀 수 있을것 같다.