[Brute Force] 백준 1018 체스판 다시 칠하기 - Python

 

[ Contents ]

 

 

1. 문제 (링크 참조)

1018번: 체스판 다시 칠하기

 

 

 

2. 문제 풀이

 N * M 크기의 보드판이 주어집니다. 보드판은 검은색과 하얀색이 뒤섞여있으며, 체스판으로 사용하기 위해서는 덧칠이 필요할 수 있습니다. 8X8 체스판을 만들기 위해서 필요한 최소 덧칠 횟수를 구하는 문제입니다.

 

2022.01.16 - [Algorithm] - [Algorithm] 브루트 포스(Brute Force)는 노가다 기법?

[Algorithm] 브루트 포스(Brute Force)는 노가다 기법?

 우선 8X8 범위의 보드판 내에서, 체스판이 되기위해 필요한 덧칠 횟수를 구해야 합니다. 체스판은 흰색과 검은색이 번갈아 나타나야 하며, 경우의 수는 2가지입니다.

 맨 처음 칸이 검은색으로 시작하는 경우와, 하얀색으로 시작하는 경우입니다. 두 가지 경우 중에 덧칠 횟수가 적은 걸 선택하면 됩니다.

 

 

 위 체스판은 첫번째 칸이 검은색일 경우입니다. 체스 칸 안에는 행과 열(i+j)을 더한 수를 적었습니다. 검은색과 흰색이 번갈아 나와야 하므로, 짝수 칸은 검은색이고 홀수 칸은 하얀색이 됩니다.

 임의로 주어지는 보드판에서, 2가지 경우를 모두 계산하고 적은 덧칠 횟수를 반환합니다.

 

 

 

3. 코드

import sys
input = sys.stdin.readline

# 입력
N, M = map(int, input().split())
row = []
for i in range(N):
    row.append(input().rstrip())

 행과 열이 있는 보드판을 입력받기 위해서 2차원 리스트를 사용합니다.

 리스트 안에 리스트를 넣어서 입력받습니다.

 

 

def chess(row, N, M):
    white = 0  # 첫 칸이 흰색일 경우 다시 칠해야하는 정사각형 수
    black = 0  # 첫 칸이 검은색일 경우 다시 칠해야하는 정사각형 수
    for i in range(N, N+8):
        for j in range(M, M+8):
            #짝수칸
            if (i+j) % 2 == 0:
                if row[i][j] == 'W':
                    black += 1
                elif row[i][j] == 'B':
                    white += 1
            #홀수칸
            if (i+j) % 2 == 1:
                if row[i][j] == 'W':
                    white += 1
                elif row[i][j] == 'B':
                    black += 1
    return min(white, black)

 8X8 범위 보드판에서 필요한 덧칠 횟수를 구하는 함수입니다. 첫 칸이 흰색일 경우와 검은색일 경우를 고려합니다. 

 첫 칸(0+0, 짝수칸)을 흰색으로 두는 white 변수는 "짝수 칸이 검은색이거나, 홀수 칸이 흰색"일 때 덧칠을 해야 합니다. 반면 첫 칸을 검은색을 두는 black 변수는 "짝수 칸이 흰색이거나, 홀수 칸이 검은색"일 때 덧칠을 합니다.

 

 

res = 65 #결과값
for i in range(N-7):
    for j in range(M-7):
        sub = chess(row, i, j)
        if sub < res:
            res = sub
print(res)

 입력 범위는 8X8 보다 크게 주어질 수 있습니다. 한 칸씩 이동하면서, 모든 경우의 8X8 보드판을 고려합니다.

 위 반복문은 왼쪽 상단 첫 칸을 기준으로 8X8 범위의 보드판을 판정합니다.

 

 

 9 X 9 보드판을 예로 들면, 총 4가지 경우를 확인해야 합니다. 위 보드판에서 8X8 체스판이 될 수 있는 경우의 수는 총 4가지입니다. 위 반복문은 왼쪽 상단의 칸을 기준으로 순환하며 계산합니다.

 

 

<전체 코드>

import sys
input = sys.stdin.readline

# 입력
N, M = map(int, input().split())
row = []
for i in range(N):
    row.append(input().rstrip())

def chess(row, N, M):
    white = 0  # 첫 칸이 흰색일 경우 다시 칠해야하는 정사각형 수
    black = 0  # 첫 칸이 검은색일 경우 다시 칠해야하는 정사각형 수
    for i in range(N, N+8):
        for j in range(M, M+8):
            #짝수칸
            if (i+j) % 2 == 0:
                if row[i][j] == 'W':
                    black += 1
                elif row[i][j] == 'B':
                    white += 1
            #홀수칸
            if (i+j) % 2 == 1:
                if row[i][j] == 'W':
                    white += 1
                elif row[i][j] == 'B':
                    black += 1
    return min(white, black)

res = 65 #결과값
for i in range(N-7):
    for j in range(M-7):
        sub = chess(row, i, j)
        if sub < res:
            res = sub
print(res)