(Python) 백준 1018번 : 체스판 다시 칠하기

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

1018번: 체스판 다시 칠하기

• 알고리즘 분류
  • 브루트 포스
  • 시뮬레이션

내가 할 수 있는 모든 방법을 동원해서 가장 Brute Force하게 풀어봤더니 예상대로 시간을 많이 잡아먹더라..

 

(Python) 백준 1018번 : 체스판 다시 칠하기¶

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

• 입력
  첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.

• 출력
  첫째 줄에 지민이가 다시 칠해야 하는 정사각형 개수의 최솟값을 출력한다.

---

In [1]:

## 입력값 받기
N,M = map(int, input().split())
first_map = [list(input()) for _ in range(N)]

10 13
BBBBBBBBWBWBW
BBBBBBBBBWBWB
BBBBBBBBWBWBW
BBBBBBBBBWBWB
BBBBBBBBWBWBW
BBBBBBBBBWBWB
BBBBBBBBWBWBW
BBBBBBBBBWBWB
WWWWWWWWWWBWB
WWWWWWWWWWBWB

In [2]:

first_map

Out[2]:

[['B', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'W', 'B', 'W', 'B', 'W'],
 ['B', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'W', 'B', 'W', 'B'],
 ['B', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'W', 'B', 'W', 'B', 'W'],
 ['B', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'W', 'B', 'W', 'B'],
 ['B', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'W', 'B', 'W', 'B', 'W'],
 ['B', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'W', 'B', 'W', 'B'],
 ['B', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'W', 'B', 'W', 'B', 'W'],
 ['B', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'W', 'B', 'W', 'B'],
 ['W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'B', 'W', 'B'],
 ['W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'B', 'W', 'B']]

In [3]:

### 'W'로 시작하는 체스판
start_w = [['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'],
 ['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'],
 ['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'],
 ['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'],
 ['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'],
 ['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'],
 ['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'],
 ['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W']]

## 'B'로 시작하는 체스판 
start_b =[['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'],
 ['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'],
 ['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'],
 ['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'],
 ['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'],
 ['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'],
 ['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'],
 ['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B']]

In [4]:

## 현재 체스판을 얼마나 수정해줘야 하는가?
def compare(start_w, start_b, map_x):
    w_cnt = 0
    b_cnt = 0
    for i in range(8):
        for j in range(8):
            if start_w[i][j] != map_x[i][j]:
                w_cnt = w_cnt + 1
            if start_b[i][j] != map_x[i][j]:
                b_cnt = b_cnt + 1
    return min(w_cnt, b_cnt)

In [5]:

min_answer = 64

## x,y는 잘라내고자 하는 체스판의 첫 시작위치(맨 왼쪽, 맨 위)
for x in range(0, N-7):
    for y in range(0, M-7):
        ## 8*8 크기의 체스판으로 잘라내기
        second_map = []
        second_map.append(first_map[x][y:y+8])
        second_map.append(first_map[x+1][y:y+8])
        second_map.append(first_map[x+2][y:y+8])
        second_map.append(first_map[x+3][y:y+8])
        second_map.append(first_map[x+4][y:y+8])
        second_map.append(first_map[x+5][y:y+8])
        second_map.append(first_map[x+6][y:y+8])
        second_map.append(first_map[x+7][y:y+8])
        
        ## 최솟값 구하기
        answer = compare(start_w, start_b, second_map)
        if min_answer > answer:
            min_answer = answer
        
        second_map.clear()

In [6]:

min_answer

Out[6]:

12