[DFS/BFS/완전탐색] 1018번 - 체스판 다시 칠하기(완전탐색)

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

풀이 시간: 40분 이내

 

1) 문제 해결 아이디어

n * m 의 보드에서 8 * 8의 크기로 잘라 체스판 처럼 인접한 검정색, 흰색이 번갈아가게 색을 칠해야 한다.

다시 칠해야하는 칸의 최소 개수를 구하는 문제로 모든 경우의수를 확인해봐야하는 완전탐색 문제다.

 

<2차원 리스트 Slicing>

n * m 의 2차원 리스트에서 r * c의 2차원 리스트를 추출하는 방법이다.

1. for문 이용

아래의 글에 의하면 numpy를 이용하면 쉽게 구할 수 있지만 코딩테스트에서는 보통 라이브러리 사용을 못하는 경우가 많으므로 꼭 기억해두자!!

graph = [[0] * m for _ in range(n)]	# n * m

# n * m 2차원 리스트에서 r * c 2차원 리스트 추출하기
for i in range(n - r + 1):
  for j in range(m - c + 1):
    board = [row[j: j + c] for row in graph[i: i + r]]

 

[참고] https://blex.me/@mildsalmon/%ED%8C%8C%EC%9D%B4%EC%8D%AC-2%EC%B0%A8%EC%9B%90-%EB%A6%AC%EC%8A%A4%ED%8A%B8-%EC%8A%AC%EB%9D%BC%EC%9D%B4%EC%8B%B1

 

 

 

 

 

파이썬 2차원 리스트 슬라이싱 — mildsalmon

 

2) 소스코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())  # 세로, 가로
# n * m(W: 흰색, B: 검정색)
graph = [list(input().strip()) for _ in range(n)]
min_cnt = 1e9  # 다시 칠해야 하는 칸의 최솟값

# 입력받은 2차원 리스트에서 8 * 8 2차원 리스트 추출해서 검사
for i in range(n - 7):
  for j in range(m - 7):
    # 8 * 8 추출하기
    board = [row[j: j + 8] for row in graph[i: i + 8]] 
    cntB, cntW = 0, 0  # 다시 칠해야하는 정사각형 개수
    for r in range(8):
      for c in range(8):
        # 짝수행, 짝수열 혹은 홀수행, 홀수열
        if (r % 2 == 0 and c % 2 == 0) or (r % 2 == 1 and c % 2 == 1):
          # 검정색으로 칠하기
          if board[r][c] == 'W':  cntB += 1
          # 흰색으로 칠하기
          else: cntW += 1
        # 짝수행, 홀수열 혹은 홀수행, 짝수열
        else:
          # 흰색으로 칠하기
          if board[r][c] == 'B':  cntB += 1
          # 검정색으로 칠하기
          else:  cntW += 1
    min_cnt = min(min_cnt, cntB, cntW)
print(min_cnt)