[Python] 1018번 : 체스판 다시 칠하기

 

문제 3줄 요약

1. 8x8 체스판을 만들 것이다. 검은색,흰색 패턴인지 흰색,검은색 패턴인지 고려해야한다.

2. 틀린 패턴이 있다면 다시 색칠한다.

3. 크기가 다양한 체스판에서 최소한으로 고쳐서 색칠하여 만들 때, 수정하는 최솟값을 구하자!

 

알고리즘 분류가

브루트포스 알고리즘이었다. 

 

즉, 완전탐색 알고리즘,

모든 경우의 수를 탐색하면서 요구 조건에 충족되는 결과만 가져오는 알고리즘이다.

 

따라서

틀을 먼저 만들고

필요한 모든 조건을 생각해보자!

 

#  N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수 입력
V,W = map(int, input().split())

chess = []
count = 0
count_list = []
color_list = ["W","B"]

if __name__ == "__main__" :
  
    # 보드판 입력
    for i in range(V):
        BW = str(input())
        chess.append(BW)

체스판의 크기를 입력 받고

칠해져 있는 체스판을 입력받는다.

 

우리가 고려해야할 조건은

1. 보드판 첫 칸의 색에 따른 탐색

2. 8x8이 아닐 때엔 옮겨다니며 탐색

 

   # 보드판의 시작이 백색 or 흑색
    for color in color_list:
      
        # baseV, baseW는 보드판이 8x8가 아닐 경우, 옮겨서 탐색
        for baseV in range(V-8+1):
            for baseW in range(W-8+1):

 

마지막으로

근본적인 문제인

번갈아 잘 색칠 되어있는지 확인해본다!

 

		# 8x8 보드판 짝수 열 탐색
                for vertical in range(0,8,2):
                    for width in range(8):
                        check = str(chess[baseV+vertical])[baseW+width]
                        # 색이 번갈아 칠해져있는지 탐색
                        if ((baseW+width) % 2) == (baseW % 2):
                            if color != check:
                                count += 1
                        elif (baseW+width) % 2 != (baseW % 2):
                            if color == check:
                                count += 1
                                
                # 8x8 보드판 홀수 열 탐색
                for vertical in range(1,8,2):
                    for width in range(8):
                        check = str(chess[baseV+vertical])[baseW+width]
                        # 색이 번갈아 칠해져있는지 탐색
                        if (baseW+width) % 2 == (baseW % 2):
                            if color == check:
                                count += 1
                        elif (baseW+width) % 2 != (baseW % 2):
                            if color != check:  
                                count += 1

 

이제 모든 다시 칠해야하는 경우의 수를 count 하여

list에 담아주고 최솟값을 구한다!

 

                # 경우의 수 마다 잘못 칠해져 있는 count 저장
                count_list.append(count)
                count = 0
                
    # 가장 적은 경우의 수 출력
    print(min(count_list))

 

결과

 

 

짜잔

 

큰 어려움 없이 1 코인에 맞춘 문제이다.

하지만

완성된 코드를 보니

효율은 좀 떨어질 것 같다는 생각이 들었다.

 

 

 

완성된 코드

 

#  N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수 입력
V,W = map(int, input().split())

chess = []
count = 0
count_list = []
color_list = ["W","B"]

if __name__ == "__main__" :
  
    # 보드판 입력
    for i in range(V):
        BW = str(input())
        chess.append(BW)

    
    # 보드판의 시작이 백색 or 흑색
    for color in color_list:
      
        # baseV, baseW는 보드판이 8x8가 아닐 경우, 옮겨서 탐색
        for baseV in range(V-8+1):
            for baseW in range(W-8+1):
                
                # 8x8 보드판 짝수 열 탐색
                for vertical in range(0,8,2):
                    for width in range(8):
                        check = str(chess[baseV+vertical])[baseW+width]
                        # 색이 번갈아 칠해져있는지 탐색
                        if ((baseW+width) % 2) == (baseW % 2):
                            if color != check:
                                count += 1
                        elif (baseW+width) % 2 != (baseW % 2):
                            if color == check:
                                count += 1
                                
                # 8x8 보드판 홀수 열 탐색
                for vertical in range(1,8,2):
                    for width in range(8):
                        check = str(chess[baseV+vertical])[baseW+width]
                        # 색이 번갈아 칠해져있는지 탐색
                        if (baseW+width) % 2 == (baseW % 2):
                            if color == check:
                                count += 1
                        elif (baseW+width) % 2 != (baseW % 2):
                            if color != check:  
                                count += 1
                # 경우의 수 마다 잘못 칠해져 있는 count 저장
                count_list.append(count)
                count = 0
                
    # 가장 적은 경우의 수 출력
    print(min(count_list))

 

조금 더 효율적으로 짤 수 있는 코드를 생각해보고

수정해보자!