💡 브루트포스

브루트 포스란?
발생할 수 있는 모든 경우를 무식하게 탐색한다는 의미이다. 완전 탐색이라고도 한다.

종류
선형구조를 전체 탐색하는 방법으로는 순차탐색이 있고,
비선형 구조를 전체 탐색하는 방법으로는 BFS(넓이 우선 탐색), DFS(깊이 우선 탐색)가 있다.

📢 1018번 - 체스판 다시 칠하기

백준 문제 링크

🔎 풀이

사용한 언어: python

1. 시작하는 위치에 따라 색을 다시 칠해야 할 칸의 개수가 달라진다.
   보드의 크기는 N X M이지만 체스판의 크기는 8X8로 고정되어있으므로,
   반복문을 통해 시작점을 (i,j)로 잡은 후 각각의 결과를 구한다.

2. 체스판 시작이 w일 경우와 b일 경우 다시 칠해야 할 체스판의 개수를 각각
   count_w와 count_b에 저장한다.

3. board[짝수][짝수] = board[홀수][홀수]
   즉, 인덱스 합이 짝수끼리 같은 색이 칠해져 있다.

   또한 인덱스 합이 홀수끼리 같은 색이 칠해져있다.

풀이 참고 링크
풀이 참고 링크2

🔎 코드

# 10단계, 실버 단계, 브루트 포스
# 체스판 다시 칠하기
# 입력 첫번째 줄 : 체스판 크기
# 입력 두번째 줄 ~ : 칠해진 체스판 색 (B:검은색, W :흰색)

import sys
n, m = map(int, sys.stdin.readline().split())  # 체스판 크기 입력받기
board = [sys.stdin.readline().strip() for _ in range(n)]
result = []

# 8x8체스판이므로 시작하는 위치에 따라 결과값이 바뀌므로
# 인덱스를 +1 해가며 결과를 구한다.
for i in range(n-7):
    for j in range(m-7):
        # count_w : 맨처음(0,0)이 W로 시작하였을 때 다시 칠해햐 되는 개수
        # count_b : 맨처음(0,0)이 B로 시작하였을 때 다시 칠해야 되는 개수
        count_w, count_b = 0, 0
        # 크기가 8*8인 체스판 각각 검사하기
        for x in range(i, i+8):
            for y in range(j, j+8):
                # 인덱스의 합이 짝수인 경우 같은 색을 가진다.
                if (x+y) % 2 == 0:
                    if board[x][y] != "W":
                        count_w += 1
                    else:
                        count_b += 1
                # 인덱스 합이 홀수인 경우 또한 같은 색을 가진다.
                else:
                    if board[x][y] != "W":
                        count_b += 1
                    else:
                        count_w += 1
        result.append(count_w)
        result.append(count_b)

# 가장 작은 수 출력
print(min(result))