완전 탐색(Brute-force Search)

아마 solved.ac를 통해서 문제를 풀다보면 구현이나 수학 문제를 제외하고 가장 처음 접하는 알고리즘일 것이다. (주위에 물어보면 그래도 들어는 봤다라고 하는 사람이 많았다.)

이름은 거창하지만 이 기법은 모든 가능성을 빠짐없이 탐색하는 방법이다. 이 표현도 다시 표현하면 노가다 정도로 말할 수 있겠다.

사실 일반 구현문제하고 비슷하다. 브루트 포스라고 해서 특별한 방법이 있는 것이 아니라 가능한 모든 경우의 수를 전부 확인할 수 있도록 코드를 짜면 그게 Brute force 탐색이다.

그럼 속으로 그냥 다 해보면 되는거니까 완전 쉬운거 아닌가? 라고 생각할 수 있는데 다 탐색하도록 코드를 구상하는 것이 생각보다 쉽지 않다. 구현력을 상당히 많이 필요로 하는 알고리즘이다. 코딩테스트에서도 거의 빠짐없이 출제되고 있으므로 반복숙달을 통해 구현력을 길러야 한다.

 

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

1018번: 체스판 다시 칠하기

체스판 다시 칠하기 문제를 봐보자.

이 문제는 solved.ac의 Class2에 있는 첫번째 문제로 Class1을 다 풀고 올라오는 초심자들이 많이 좌절하는 문제이기도 하다. 문제를 보고 오지 않았다면 꼭 문제를 보고 시도해보고 다시 오기를 추천한다.

 

본인이 혹시 이전까지는 문제를 보자마자 코드를 작성하면서 생각했다면, 지금부터는 어떤식으로 코드를 구성해 나갈 것인지 고민하고 시작하는게 좋다.

이 문제는 8 × 8의 체스판을 만드는데 최소로 정사각형을 다시 칠하는 횟수를 출력해야 한다.

문제에서 나왔듯이 체스판에는 맨 처음이 흰색으로 시작하는 체스판과 검은색으로 시작하는 체스판 총 두가지 종류가 있다.

아까 Brute force기법이 뭐라고 했는지 기억해보자 --> "하나도 빠짐없이 모든 경우의 수를 탐색" 따라서 8*8체스판에서 처음이 흰색인 경우와 검정색인 경우를 모두 따져주어야 한다.

 

보통 처음 풀때 처음이 흰색으로 되있으면 흰색인 경우만 탐색하고 검은색이면 검은색인 경우만 탐색하는 사람들이 꽤 있다. 하지만 첫번째를 바꿔서 다시 칠하는 경우의 수가 있기 때문에 두 경우를 모두 고려해 주어야 한다.

 

그리고 주어진 판의 크기가 8 × 8으로 주어지지 않을 수도 있으므로 판을 8 × 8만 탐색하도록 하는 반복문도 필요하다.

 

 

 

 

 

 

다음의 경우만 보아도 첫번째 칸 검은색을 흰색으로 바꾸는 경우가 처음을 검은색으로 고정하고 나머지를 바꾸는 경우보다 적다.

 

 

 

 

 

 

 

 

 

결론

1. 주어진 칸을  가로 세로 8칸씩 탐색할 수 있도록 반복문을 구성한다.

2. 첫번째 칸이 검은색인 경우와 흰색인 경우의 체스판을 만든다고 가정하고 둘중 다시 칠하는 횟수가 적은 걸 선택한다.

3. 주어진 판이  8 × 8이 아닌 경우 나머지  8 × 8체스판에 대해서도 모두 2번 과정을 거쳐서 최종적으로 가장 적은 횟수를 구한다.

 

 

 

 

코드는 다음과 같다.

import sys
n, m = map(int,sys.stdin.readline().split())
board_entire = [list(sys.stdin.readline().rstrip()) for _ in range(n)]
minimun = []
board_slice = []

##체스판을 탐색하여 다시 칠하는 횟수를 구하는 함수(시작이 흰색인 경우)
def cnt_W(board):
  count =0
  for i in range(8):
    for j in range(8):
      if (i+j) % 2 == 0 and board[i][j] != 'W':
        count +=1 
      elif (i+j) % 2 ==1 and board[i][j] != 'B':
        count +=1 
  return count

##체스판을 탐색하여 다시 칠하는 횟수를 구하는 함수(시작이 검은색인 경우)
def cnt_B(board):
  count =0
  for i in range(8):
    for j in range(8):
      if (i+j) % 2 == 0 and board[i][j] != 'B':
        count +=1 
      elif (i+j) % 2 ==1 and board[i][j] != 'W':
        count +=1 
  return count

##주어진 판을 8*8범위만 탐색하는 반복문
for i in range(n-7):
  for j in range(m-7):
    for k in range(8):
      board_slice.append(board_entire[i+k][j:j+8])
    minimun.append(cnt_W(board_slice))
    minimun.append(cnt_B(board_slice))
    board_slice = []

##구한 최소로 다시 칠하는 횟수중에 가장 작은 것을 출력
print(min(minimun))

 

 

 

Brute-Force Search 에 대해서 글을 썼는데 체스판 다시 칠하기 문제의 설명을 보시면 알겠지만 딱히 특별한 방법없이 말 그대로 체스판을 만들수 있는 모든 경우를 다 탐색하여 정답을 구했다.

가능한 모든 경우를 빠짐없이 탐색하는 것이 Brute-Force 기법이자 완전탐색이다.