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

출처

백준 1018번 체스판 다시 칠하기

---

정답

import sys


board_size = 8
b_board = []
w_board = []

for i in range(board_size):
  for j in range(board_size):
    if i % 2 == 0 and j % 2 == 0:
      b_board.append("B")
      w_board.append("W")
    elif i % 2 == 0 and j % 2:
      b_board.append("W")
      w_board.append("B")
    elif i % 2 and j % 2 == 0:
      b_board.append("W")
      w_board.append("B")
    else:  #i % 2 == 0 and j % 2:
      b_board.append("B")
      w_board.append("W")


N, M = map(int, sys.stdin.readline().rstrip().split())

board = []
for i in range(N):
  s = sys.stdin.readline().rstrip()
  board.append(s)

start_nums = []
for i in range(N - board_size + 1):
  for j in range(M - board_size + 1):
    start_nums.append((i, j))    

min_change_count = 999
for i, j in start_nums:  # 6회
  # make board
  candidate_board = []
  for k in range(i, i + 8):
    for l in range(j, j + 8):
      candidate_board.append(board[k][l])

  b_count = 0
  w_count = 0
  for k in range(8 * 8):
    if b_board[k] != candidate_board[k]:
      b_count += 1
    elif w_board[k] != candidate_board[k]:
      w_count += 1


  if b_count < min_change_count:
    min_change_count = b_count
  if w_count < min_change_count:
    min_change_count = w_count

print(min_change_count)

---

문제

---

입출력

---

풀이

0. 전략

위키백과-Brute-force search

무차별 대입 탐색 (Brute-force search) 또는 완전 탐색 (exhaustive search) 알고리즘은 문제 해결의 답이 될 수 있는 모든 후보를 나열하고, 각 후보가 문제를 해결하는 지 확인하는 방법이다.

가능한 모든 경우의 수를 확인한다 
주어진 체스판으로 만들 수 있는 모든 8x8 크기의 보드판에 대해서, 
문제를 해결할 수 있는 정답과 비교하여 차이가 가장 작은 보드판을 구한다 
즉 
1) 주어진 문제를 해결하는 정답 체스판을 만든다 (2개) 
  - 검정색 정사각형으로 시작하는 8x8 보드판 
  - 흰색 정사각형으로 시작하는 8x8 보드판
2) 주어진 보드판을 8x8 크기로 잘라준다 
3) 8x8 크기로 자른 모든 보드판을 정답 체스판과 비교한다 
4) 비교 결과 정사각형 색상 차이가 가장 작은 보드 판을 찾는다 (= 교체해야할 정사각형의 개수가 가장 작은 8 x 8로 자른 보드판)
5) 해당 보드판에서 교체해야할 정사각형 수를 출력한다 

1. 문제/입력값에 의한 초기 설정

## 1) 주어진 문제를 해결하는 정답 체스판을 만든다
# 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다
board_size = 8

# 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 
# 하나는 맨 왼쪽 위 칸이 흰색인 경우, 
# 하나는 검은색인 경우이다
b_board = []
w_board = []

# 체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 
# 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 
# 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다
for i in range(board_size):
  for j in range(board_size):
    if i % 2 == 0 and j % 2 == 0:
      b_board.append("B")
      w_board.append("W")
    elif i % 2 == 0 and j % 2:
      b_board.append("W")
      w_board.append("B")
    elif i % 2 and j % 2 == 0:
      b_board.append("W")
      w_board.append("B")
    else:  #i % 2 == 0 and j % 2:
      b_board.append("B")
      w_board.append("W")        

## 2) 주어진 보드판을 8x8 크기로 잘라준다 
# 주어진 보드판의 크기 및 보드의 색상을 입력받는다 
N, M = map(int, sys.stdin.readline().rstrip().split())
board = []
for i in range(N):
  s = sys.stdin.readline().rstrip()
  board.append(s)

# 보드판을 8x8 크기로 자를 수 있는 모든 경우의 수를 구한다 
# 각 경우의 수의 첫번째 시작점을 저장한다 
start_nums = []
for i in range(N - board_size + 1):
  for j in range(M - board_size + 1):
    start_nums.append((i, j))    

2. 다시 칠해야 하는 정사각형 수 구하기 알고리즘

## 3) 8x8 크기로 자른 모든 보드판을 정답 체스판과 비교한다 
# 다시 칠해야 하는 정사각형 개수의 최솟값은 보드판 크기보다 큰 수로 초기화한다 
min_change_count = 999

# 모든 경우의 수에 대해서 
for i, j in start_nums:  
  # 비교할 보드판을 만든다 
  candidate_board = []
  for k in range(i, i + 8):
    for l in range(j, j + 8):
      candidate_board.append(board[k][l])

  # 정답 보드와 비교한다 
  b_count = 0
  w_count = 0
  for k in range(8 * 8):
    # 검정색으로 시작하는 보드판과 비교하여 차이가 있을 때마다 1 증가 
    if b_board[k] != candidate_board[k]:
      b_count += 1
    # 흰색으로 시작하는 보드판과 비교하여 차이가 있을 때마다 1 증가 
    if w_board[k] != candidate_board[k]:
      w_count += 1

  # 검정색 정답 보드판과 비교한 차이가 min_change_count 보다 작다면 min_change_count를 변경
  if b_count < min_change_count:
    min_change_count = b_count
  # 흰색 정답 보드판과 비교한 차이가 min_change_count 보다 작다면 min_change_count를 변경
  if w_count < min_change_count:
    min_change_count = w_count

3. 정답 출력

# 모든 경우의 수에 대한 비교가 끝난 후 
# 다시 칠해야 하는 정사각형 개수의 최솟값을 출력한다.
print(min_change_count)

---

주어진 보드판으로 생성할 수 있는 모든 8x8 보드판 구하기

1) 주어진 보드판 :9 x 9

2) 모든 경우의 수 : 4

• 보드판 생성 시작 위치 : (0, 0), (0, 1), (1, 0), (1, 1)

2-1) (0, 0) 을 시작점으로 자른 보드판

2-2) (0, 1) 을 시작점으로 자른 보드판

2-3) (1, 0) 을 시작점으로 자른 보드판

2-4) (1, 1) 을 시작점으로 자른 보드판

---