[백준][Python] 1018

김영후·2022년 11월 30일
0

BOJ

목록 보기
3/4
post-thumbnail


지민이가 체스판을 만들고 싶어한다. 문제의 예제를 살펴보면

이런식으로 8X8 이상의 크기를 가진 입력이 주어지는데, 이를 8X8로 자른 후 체스판의 무늬를 만들기 위해 칠해야하는 횟수가 가장 작을 때의 횟수를 출력하는 문제다.
문제를 잘 읽어보면 "체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다." 라는 말이 있다. 처음에는 여기에 빠져 8X8로 잘랐을 때 왼쪽 제일 위의 색깔을 기준으로 색칠 횟수를 세었다. 아래는 그 코드이다.

def board_checker(board):
    num_change = 0
    if board[0][0] == "W":
        for i in range(8):
            if i%2 == 0:
                for j in range(8):
                    if j%2 == 0:
                        if board[i][j] != "W":
                            num_change += 1
                    else:
                        if board[i][j] != "B":
                            num_change += 1
            else:
                for j in range(8):
                    if j%2 == 0:
                        if board[i][j] != "B":
                            num_change += 1
                    else:
                        if board[i][j] != "W":
                            num_change += 1

                
    else:   #"B"
        for i in range(8):
            if i%2 == 0:
                for j in range(8):
                    if j%2 == 0:
                        if board[i][j] != "B":
                            num_change += 1
                    else:
                        if board[i][j] != "W":
                            num_change += 1
            else:
                for j in range(8):
                    if j%2 == 0:
                        if board[i][j] != "W":
                            num_change += 1
                    else:
                        if board[i][j] != "B":
                            num_change += 1


    return num_change


def main():
    N, M = map(int, input().split())
    origin_board = []
    result = 64
    for _ in range(N):
        origin_board.append(input())

    for i in range(M - 7):
        for j in range(N - 7):
            board = []
            for k in range(j, j+8):
                board.append(origin_board[k][i:i+8])
            num = board_checker(board)
            if num < result:
                result = num
        

    print(result)

if __name__ == "__main__":
    main()

그런데 예제들 중에는

9 23
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBW

이런 녀석이 있다. 이 경우 마지막에 자른 8X8 체스판은 오른쪽 제일 아래만 W(흰 색)인 경우인데, 이를 왼쪽 제일 위의 색깔을 기준으로 색칠 횟수를 구하면 32가 나온다. 하지만 오른쪽 제일 아래의 색을 기준으로 하면 색칠 횟수가 31이 나오는 것이다. 처음 내가 구현한 코드는 이 부분을 간과했다.
그렇다면 이 부분을 어떻게 해결할 수 있을까? 한참을 생각해보던 중 떠오른 것은 어느 한 칸을 기준으로 횟수를 세는 것이 아니라 index의 합을 이용하는 것이다. 아래 그림을 보자.

이렇게 index의 합에 따라 칸을 구분할 수 있는데, index가 (i, j)라고 할 때 (i+j) % 2 == 0(even)인 칸, (i+j) % 2 != 0(odd)인 칸 이렇게 두 가지로 나눌 수 있다. 어느 한 칸을 기준으로 한 것이 아니기에 횟수를 두 번 세어주면 된다. 하나는 index 합이 짝수인 칸이 B이고 홀수인 칸이 W인 판을 만들고 싶을 때 필요한 횟수, 하나는 index 합이 짝수인 칸이 W이고 홀수인 칸이 B인 판을 만들고 싶을 때 필요한 횟수이다. 이 두 횟수 중 작은 것을 매 8X8로 자른 판마다 구해준 후, 그 중 가장 작은 값을 최종적으로 리턴하면 되는 것이다.
아래는 그를 구현한 코드이다.

def board_checker(board):
    num_change1 = 0
    num_change2 = 0
    for i in range(8):
        for j in range(8):
            if (i+j)%2 == 0:
                if board[i][j] != "B":
                    num_change1 += 1
                if board[i][j] != "W":
                    num_change2 += 1
            else:
                if board[i][j] != "W":
                    num_change1 += 1
                if board[i][j] != "B":
                    num_change2 += 1

    return min(num_change1, num_change2)


def main():
    N, M = map(int, input().split())
    origin_board = []
    result = 64
    for _ in range(N):
        origin_board.append(input())

    for i in range(M - 7):
        for j in range(N - 7):
            board = []
            reverse_board = []
            for k in range(j, j+8):
                board.append(origin_board[k][i:i+8])
            num = board_checker(board)
            if num < result:
                result = num
        
    print(result)


if __name__ == "__main__":
    main()

기준에 너무 얽매이지 않고, 내가 이용할 수 있는 것들을 최대한 이용하는 사고를 해보는 좋은 경험이었던 것 같다.

profile
PNU CSE 16th / Busan, South Korea

0개의 댓글