[브루트 포스] 백준 - 1018번: 체스판 다시 칠하기 (파이썬)

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

 

문제

지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다.

체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.

보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8×8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8*8 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.

 

입력

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

출력

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

 

예제 입력 & 출력

8 8
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBBBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW

#출력: 1

 

 

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

#출력: 12

 

 

8 8
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB

#출력: 0

 

9 23
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBW

#출력: 31

 

 

10 10
BBBBBBBBBB
BBWBWBWBWB
BWBWBWBWBB
BBWBWBWBWB
BWBWBWBWBB
BBWBWBWBWB
BWBWBWBWBB
BBWBWBWBWB
BWBWBWBWBB
BBBBBBBBBB

#출력: 0

 

 

8 8
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBBBWBW
WBWBWBWB
BWBWBWBW
WBWBWWWB
BWBWBWBW

#출력: 2

 

11 12
BWWBWWBWWBWW
BWWBWBBWWBWW
WBWWBWBBWWBW
BWWBWBBWWBWW
WBWWBWBBWWBW
BWWBWBBWWBWW
WBWWBWBBWWBW
BWWBWBWWWBWW
WBWWBWBBWWBW
BWWBWBBWWBWW
WBWWBWBBWWBW

#출력: 15

 

---

처음 문제를 봤을 때 'BW' 문자의 개수를 세어서 많은 쪽으로 선택해야 하나? 싶었다.

하지만 여러 줄로 나누어져 있는 문자열에서 영역을 따지며 빈도 수를 세는 건 너무 어려울 것 같아서 무식하게(?) 8*8 체스판을 오른쪽 -> 아래 순으로 한 칸 씩 움직이며 탐색하는 방법을 선택했다.

 

뒤늦게 알았는데 이 방법이 브루트 포스라고 한다..

정말 이름값 하는 방법이다,,,,

 

 

 

 

체스판은 색이 번갈아 나오는 특성을 가지고 있다.

이로 인해 이용할 수 있는 핵심 아이디어는 다음과 같다.

1. (행 + 열 인덱스) % 2 == 0, 즉 행과 열의 합이 짝수이면 그 칸에는 첫 칸의 색깔과 같은 색이 들어 있다.
2. 행과 열의 합이 홀수이면 그 칸에는 첫 칸의 색깔과 다른 색이 들어 있다.

 

코드 뜯어보기

1. 전역변수 선언

n, m = map(int, input().split()) # 보드의 가로, 세로 길이
board = [list(input()) for _ in range(n)]  # 보드 값에 'B', 'W' 채움

ans = []  # 체스판을 덧칠하는 횟수를 담는 리스트

 

2. 핵심 로직

# 8*8 체스판을 오른쪽, 아래로 한 칸 씩 움직이면서 cnt 비교
# 완성된 체스판의 경우의 수는 [W로 시작하는 경우, B로 시작하는 경우] 2가지
for i in range(len(board) - 7):
    for j in range(m - 7):
        w_cnt, b_cnt = 0, 0 # white, black으로 시작할 때 다시 칠해야 하는 개수

        for row in range(i, i + 8):
            for col in range(j, j + 8):

                # 해당 칸이 black일 경우
                if board[row][col] == 'B':
                    # 첫 칸이 white인 경우
                    # 행과 열의 합이 짝수일 때 흰색으로 칠해야 함
                    if (row + col) % 2 == 0:
                        w_cnt += 1
                    # 첫 칸이 black인 경우
                    # 행과 열의 합이 홀수일 때 검정색으로 칠해야 함
                    if (row + col) % 2 != 0:
                        b_cnt += 1

                # 해당 칸이 white일 경우
                if board[row][col] == 'W':
                    if (row + col) % 2 == 0:
                        b_cnt += 1
                    if (row + col) % 2 != 0:
                        w_cnt += 1

        ans.append(w_cnt)
        ans.append(b_cnt)

 

for i in range(len(board) - 7):
    for j in range(m - 7):
        w_cnt, b_cnt = 0, 0

 

체스판 전체 길이에서 8 * 8 크기의 체스판을 잘라야 하므로 range()에 각각 -7 연산을 추가했다.

• w_cnt: 8*8 크기의 체스판에서 첫 칸이 white인 경우, 색을 덧칠하는 횟수
• b_cnt: 8*8 크기의 체스판에서 첫 칸이 black인 경우, 색을 덧칠하는 횟수

        for row in range(i, i + 8):
            for col in range(j, j + 8):

 

보드에서 시작하는 인덱스 기준으로 가로, 세로 각각 8칸 까지 탐색한다.

 

                # 해당 칸이 black일 경우
                if board[row][col] == 'B':
                    # 첫 칸이 white인 경우
                    # 행과 열의 합이 짝수일 때 흰색으로 칠해야 함
                    if (row + col) % 2 == 0:
                        w_cnt += 1
                    # 첫 칸이 black인 경우
                    # 행과 열의 합이 홀수일 때 검정색으로 칠해야 함
                    if (row + col) % 2 != 0:
                        b_cnt += 1

                # 해당 칸이 white일 경우
                if board[row][col] == 'W':
                    if (row + col) % 2 == 0:
                        b_cnt += 1
                    if (row + col) % 2 != 0:
                        w_cnt += 1

 

• 해당 칸이 black('B')일 경우
  • 그 칸의 행과 열의 합이 짝수일 경우, 해당 영역의 체스판의 첫 칸이 흰색일 때 다른 색으로 덧칠해 주어야 한다. 그러므로 w_cnt의 횟수를 +1 추가한다.
  • 그 칸의 행과 열의 합이 홀수일 경우, 해당 영역의 체스판의 첫 칸이 검정색일 때 다른 색으로 덧칠해 주어야 한다.그러므로 b_cnt의 횟수를 +1 추가한다.
• 해당 칸이 white('W')일 경우
  • 그 칸의 행과 열의 합이 짝수일 경우, 해당 영역의 체스판의 첫 칸이 검정색일 때 다른 색으로 덧칠해 주어야 한다.그러므로  b_cnt의 횟수를 +1 추가한다.
  • 그 칸의 행과 열의 합이 홀수일 경우, 해당 영역의 체스판의 첫 칸이 흰색일 때 다른 색으로 덧칠해 주어야 한다. 그러므로 w_cnt의 횟수를 +1 추가한다.

이렇게 각 체스판의 위치에 카운트를 세팅해 놓고, 8*8 체스판을 보드 안에서 한 칸 씩 이리저리 움직였을 때 cnt의 최솟값을 출력하면 된다.

        ans.append(w_cnt)
        ans.append(b_cnt)

print(min(ans))

 

전체 코드

n, m = map(int, input().split())
board = [list(input()) for _ in range(n)]

ans = []

# 8*8 체스판을 오른쪽, 아래로 한 칸 씩 움직이면서 cnt 비교
# 완성된 체스판의 경우의 수는 [W로 시작하는 경우, B로 시작하는 경우] 2가지
for i in range(len(board) - 7):
    for j in range(m - 7):
        w_cnt, b_cnt = 0, 0 # white, black으로 시작할 때 다시 칠해야 하는 개수

        for row in range(i, i + 8):
            for col in range(j, j + 8):

                # 해당 칸이 black일 경우
                if board[row][col] == 'B':
                    # 첫 칸이 white인 경우
                    # 행과 열의 합이 짝수일 때 흰색으로 칠해야 함
                    if (row + col) % 2 == 0:
                        w_cnt += 1
                    # 첫 칸이 black인 경우
                    # 행과 열의 합이 홀수일 때 검정색으로 칠해야 함
                    if (row + col) % 2 != 0:
                        b_cnt += 1

                # 해당 칸이 white일 경우
                if board[row][col] == 'W':
                    if (row + col) % 2 == 0:
                        b_cnt += 1
                    if (row + col) % 2 != 0:
                        w_cnt += 1

        ans.append(w_cnt)
        ans.append(b_cnt)

print(min(ans))

 

---

브루트 포스 문제를 처음 풀어봐서 코드를 짜다가도 뒤늦게 보면 엄청 헷갈렸었다.

그래서 내 코드를 복기할 때 내가 짠 코드도 이해를 못 해서 이상한 질문도 해버렸다😥😥😥

4중 for문,, 너무 어지러워서 나중에 함수로 따로 빼는 방법으로 리팩토링도 해 봐야 겠다.