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

파이썬 백준 1018번

실버4

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

1018번: 체스판 다시 칠하기

 

 

 

 

 

문제 보기

분류: 브루트포스 알고리즘

 

 

 

 

 

문제 풀기

규칙 모양이 정제되지 않은 2차원 리스트를 저장하고 체스판으로 형성 가능한 8 by 8 에 대해 모든 경우를 따져보고 W 또는 B 으로 변경해야 할 최솟값을 찾는다.

 

 

8 x 8 로 자를 수 있는 위치의 기준은 2차원 배열의 왼쪽 위의 index 를 기준으로 하여 그 경우를 area_N 과 area_M 으로 모두 따져본다. 이때, 첫 index 의 값이 white 또는 black 의 경우에 대해 색칠해야 하는 개수를 모두 알아보기 위해 변수를 지정한다.

    for area_N in range(N - 7):
        for area_M in range(M - 7):
            start_white = 0
            start_black = 0

 

8 x 8 의 크기가 가능한 기준을 위 for loop 에서 정했으면, 이를 이용하여 8 x 8 내부의 W B 체스판 형성 조건을 구한다.

체스판 행렬의 index 합이 짝수 또는 홀수가 번갈아 이루어지는 위치와 체스판을 형성하기 위한 white black 가 번갈아 칠해지는 위치는 같기 때문에 2 로 나눈 나머지가 0 인지 1 인지에 따라 그 조건문을 지정하고 색을 다시 칠할지 말지를 count 한다.

            for selected_A in range(area_N, area_N+8):
                for selected_B in range(area_M, area_M+8):
                    if (selected_A + selected_B) % 2 == 0:
                        if board[selected_A][selected_B] != 'W':
                            start_white += 1
                        if board[selected_A][selected_B] != 'B':
                            start_black += 1
                    elif (selected_A + selected_B) % 2 == 1:
                        if board[selected_A][selected_B] != 'B':
                            start_white += 1
                        if board[selected_A][selected_B] != 'W':
                            start_black += 1

 

시작 색 white 또는 black 으로 다시 칠해야 하는 횟수를 저장한 start_white, start_black 의 값을 빈 painted = [] 리스트에 저장하고 그 중 최솟값을 return 한다.

            painted.append(start_white)
            painted.append(start_black)
            
    return min(painted)

 

 

 

 

 

코드 보기

import sys
inputdata = sys.stdin.readline

def fnRepaint(N, M, board):
    painted = []
    for area_N in range(N - 7):
        for area_M in range(M - 7):
            start_white = 0
            start_black = 0
            
            for selected_A in range(area_N, area_N+8):
                for selected_B in range(area_M, area_M+8):
                    if (selected_A + selected_B) % 2 == 0:
                        if board[selected_A][selected_B] != 'W':
                            start_white += 1
                        if board[selected_A][selected_B] != 'B':
                            start_black += 1
                    elif (selected_A + selected_B) % 2 == 1:
                        if board[selected_A][selected_B] != 'B':
                            start_white += 1
                        if board[selected_A][selected_B] != 'W':
                            start_black += 1
            painted.append(start_white)
            painted.append(start_black)
            
    return min(painted)


if __name__ == "__main__":
    N, M = map(int, inputdata().split())
    board = [list(str(inputdata().strip())) for _ in range(N)]
    print(board)            # test print

    result = fnRepaint(N, M, board)
    print(result)



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


# [
#     ['B', 'W', 'W', 'B', 'W', 'W', 'B', 'W', 'W', 'B', 'W', 'W'], 
#     ['B', 'W', 'W', 'B', 'W', 'B', 'B', 'W', 'W', 'B', 'W', 'W'], 
#     ['W', 'B', 'W', 'W', 'B', 'W', 'B', 'B', 'W', 'W', 'B', 'W'], 
#     ['B', 'W', 'W', 'B', 'W', 'B', 'B', 'W', 'W', 'B', 'W', 'W'], 
#     ['W', 'B', 'W', 'W', 'B', 'W', 'B', 'B', 'W', 'W', 'B', 'W'], 
#     ['B', 'W', 'W', 'B', 'W', 'B', 'B', 'W', 'W', 'B', 'W', 'W'], 
#     ['W', 'B', 'W', 'W', 'B', 'W', 'B', 'B', 'W', 'W', 'B', 'W'], 
#     ['B', 'W', 'W', 'B', 'W', 'B', 'W', 'W', 'W', 'B', 'W', 'W'], 
#     ['W', 'B', 'W', 'W', 'B', 'W', 'B', 'B', 'W', 'W', 'B', 'W'], 
#     ['B', 'W', 'W', 'B', 'W', 'B', 'B', 'W', 'W', 'B', 'W', 'W'], 
#     ['W', 'B', 'W', 'W', 'B', 'W', 'B', 'B', 'W', 'W', 'B', 'W']
# ]


# 15