백준 - 1018번 체스판 다시 칠하기 python 문제풀이 [Hellfer]

728x90

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

1018번: 체스판 다시 칠하기

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

www.acmicpc.net

🔷 알고리즘 분류 - 브루트포스 알고리즘 난이도 - 실버 4

🔶 문제 이해하기 - 시간 복잡도는 O((N-7) * (M-7) * 8 * 8)

이 문제는 크기가 MxN인 체스판이 주어지고, 이 체스판의 각 칸은 검은색('B') 또는 흰색('W')으로 칠해져 있습니다.

이 체스판을 8x8 크기로 자른 후, 이 부분 체스판을 검은색 또는 흰색으로 시작하는 정상적인 체스판으로 바꾸려고 합니다.

정상적인 체스판은 다음 두 가지 중 하나입니다:

● 첫 번째 칸이 흰색인 경우: 첫 번째 칸을 기준으로 오른쪽으로 한 칸씩 이동할 때마다 색이 번갈아 바뀝니다.

또한, 첫 번째 행에서 아래로 한 행씩 내려갈 때마다 첫 번째 칸의 색이 번갈아 바뀝니다.

● 첫 번째 칸이 검은색인 경우: 첫 번째 칸을 기준으로 오른쪽으로 한 칸씩 이동할 때마다 색이 번갈아 바뀝니다.

또한, 첫 번째 행에서 아래로 한 행씩 내려갈 때마다 첫 번째 칸의 색이 번갈아 바뀝니다.

이 문제에서는 주어진 체스판을 8x8 크기로 자른 후, 이 부분 체스판을 정상적인 체스판으로 바꾸는 데 필요한 최소

변경 횟수를 찾아야 합니다.

변경 횟수는 잘못된 색으로 칠해진 칸을 올바른 색으로 바꾸는 횟수입니다.

또한, 문제에서는 가능한 모든 8x8 크기의 부분 체스판에 대해 계산을 수행하고, 그중 최소 변경 횟수를 출력해야 합니다.

이는 주어진 체스판이 8x8보다 클 수 있기 때문입니다. 이 경우, 가능한 모든 8x8 부분 체스판을 순회하며 최소 변경 횟수를 찾아야 합니다.

🔶문제풀이 - 브루트포스 알고리즘을 이용한 풀이

 행과 열의 크기를 입력받습니다.
N, M = map(int, input().split())

# 체스판의 상태를 입력받습니다.
board = [list(input()) for _ in range(N)]
result = []

# 체스판의 모든 8x8 부분을 순회합니다.
for i in range(N-7):
    for j in range(M-7):
        w = 0  # 'W'로 시작하는 체스판을 만들기 위해 필요한 변경 횟수
        b = 0  # 'B'로 시작하는 체스판을 만들기 위해 필요한 변경 횟수
        for k in range(i, i+8):
            for l in range(j, j+8):
                # (k, l)이 짝수 위치에 있을 경우
                if (k+l)%2 == 0:
                    # 'W'가 아니라면 'W'로 변경해야 하므로 w를 1 증가시킵니다.
                    if board[k][l] != 'W': w += 1  
                    # 'B'가 아니라면 'B'로 변경해야 하므로 b를 1 증가시킵니다.
                    if board[k][l] != 'B': b += 1
                # (k, l)이 홀수 위치에 있을 경우
                else :
                    # 'B'가 아니라면 'B'로 변경해야 하므로 w를 1 증가시킵니다.
                    if board[k][l] != 'B': w += 1
                    # 'W'가 아니라면 'W'로 변경해야 하므로 b를 1 증가시킵니다.
                    if board[k][l] != 'W': b += 1
        # 변경 횟수를 result 리스트에 추가합니다.
        result.append(w)
        result.append(b)

# result 리스트에서 최소값을 출력합니다.
print(min(result))

🔶 문제 해결전략

체스판의 모든 8x8 부분을 순회하며, 각 부분 체스판을 'W'로 시작하는 체스판과 'B'로 시작하는 체스판 중 어느 것으로 만드는 데 더 적은 변경이 필요한지를 찾아야 합니다.

예를 들어 10x13의 크기의 체스판이 있다고 가정해 봅시다.

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

우선, 첫 번째 8x8 부분 체스판을 살펴봅시다.

BBBBBBBB
BBBBBBBB
BBBBBBBB
BBBBBBBB
BBBBBBBB
BBBBBBBB
BBBBBBBB
BBBBBBBB

'W'로 시작하는 체스판으로 만들기 위해서는 모든 'B' 위치를 'W'로 바꿔야 합니다. 따라서 변경 횟수 w는 64가 됩니다.

또한, 이 체스판을 'B'로 시작하는 체스판으로 만들기 위해서는 체스판의 홀수 위치에 있는 'B'를 'W'로 바꿔야 합니다. 홀수 위치는 체스판의 절반에 해당하므로, 변경 횟수 b는 32가 됩니다.

따라서 이 경우, 'B'로 시작하는 체스판으로 만드는 것이 더 적은 변경을 필요로 합니다.

이제 두 번째 8x8 부분 체스판을 살펴봅시다.

BBBBBWBW
BBBBBWBW
BBBBBWBW
BBBBBWBW
BBBBBWBW
BBBBBWBW
BBBBBWBW
WWWWWWBW

이후 반복문을 수행하면서 이처럼, 각 8x8 부분 체스판에 대해 'W'로 시작하는 체스판을 만드는 데 필요한 변경 횟수와 'B'로 시작하는 체스판을 만드는 데 필요한 변경 횟수를 계산하고, 둘 중 더 작은 값을 선택하면 체스판을 만드는 데 필요한 최소 변경 횟수를 얻을 수 있습니다.

🤗파이팅입니다~ 여러분!!🤗