백준 1018번 - 체스판 다시 칠하기

코테 풀이들은 대부분 길어서 더보기 클릭을 하지 않으면 보이지 않도록 해당 문구를 추가합니다.

백준 1018: 체스판 다시 칠하기

문제 출처 : https://www.acmicpc.net/problem/1018

문제 설명

일단 문제를 읽고 체스판 자체를 코드로 구현해야 한다.
그리고 체스판을 구성할 수 있는 모든 경우의 수를 다 세어가면서 (브루트 포스) 최소 값을 구하면 되는 문제이다.
체스판을 칠할 때, 먼저 8 by 8 체스판을 구성할 수 있는 모든 경우의 수를 파악하고
이후 해당 체스판을 픽한 후 그 체스판을 칠할 수 있는 모든 경우의 수를 계산한다.
브루트 포스 문제는 모든 경우를 빠지지 않고 검사하였는지 꼼꼼히 따져보는 것이 핵심!!

문제 풀이

[플이 논리]
1. 8 by 8 체스판 몇개를 구성할 수 있는지 for문을 통해 파악한다.
2. 이 때, 시작점으로 할 수 있는 정사각형의 경우의 수를 세면 편하다.
3. 다 세었다면, 딱 하나의 경우로 fix한 후 그 board를 체스판으로 만들려면 최소 몇개를 칠해야 하는지 계산하는 함수를 구성한다.
4. 체스판으로 만들 수 있는 모든 경우를 세려면, 시작점이 B인 체스판 구성 또는 시작점이 W인 체스판 구성 이렇게 두가지만 세어주면 모든 경우가 커버된다.
5. 해당 경우에 최소 몇번의 정사각형을 칠해야 하는지 각각 세어서 리턴해주면 종료!

def make_chess_board(i,j):
    """
    starting point : (i,j)
    start_white : W로 시작하는 체스판을 구성하는 경우, 칠해야 하는 최소 정사각형 개수
    start_black : B로 시작하는 체스판을 구성하는 경우, 칠해야 하는 최소 정사각형 개수
    """
    # 초기화
    start_white, start_black = 0, 0

    # for loop 으로 보드 전체 탐색
    for x in range(i, i+8):
        for y in range(j, j+8):
            if (x + y) % 2 == 0: # 징검다리 탐색을 위한 테크닉
                if board[x][y] == "W": # 시작점이 W이면,
                    start_black += 1 # 시작을 B로 하는 체스판 만들려면 칠해야함
                else: # 시작점이 B이면,
                    start_white += 1 # 시작을 W로 하는 체스판 만들려면 칠해야함

            else:
                if board[x][y] == "B": # 두번째 칸이 B이면,
                    start_black += 1 # 시작을 B로 하는 체스판 만들려면 W로 칠해야함
                else: # 두번째 칸이 W이면,
                    start_white += 1 # 시작을 W로 하는 체스판 만들려면 B로 칠해야함

    return start_white, start_black


if __name__ == "__main__":
    import sys; readline = sys.stdin.readline
    N, M = map(int, readline().split())
    board = []
    for _ in range(N):
        board.append([i for i in readline().strip()])

    # 시작점 경우의 수 계산하기
    answer = []
    for i in range(N-8+1):
        for j in range(M-8+1):
            # 시작점이 (i,j) 인 체스 보드
            start_white, start_black = make_chess_board(i,j)
            answer.append(min(start_white, start_black))

    # 최종적으로 min값 선정
    print(min(answer))