[python] 1018. 체스판 다시 칠하기

• 문제 

---

---

 

 

• 올바른 풀이

N, M = map(int, input().split())
board = [] # 전체 보드를 나타내기 위함
result = [] # 결과값을 나타내기 위함

for i in range(N):
    board.append(input())

# 칠할 체스는 8*8
for i in range(N-7): # i,j는 체스판의 칠할 부분을 찾는 시작점
    for j in range(M-7):
        black_first = 0 # 시작 지점이 검은색일 경우
        white_first = 0 # 시작 지점이 흰색일 경우

        # 자른 체스판을 처음부터 검사
        for a in range(i, i+8):
            for b in range(j, j+8):
                if (a+b) % 2 == 0: # 어느색을 칠할지 결정
                    if board[a][b] != 'B':
                        black_first += 1 # 검은색이 아닐때 1을 더하여 색칠
                    if board[a][b] != 'W':
                        white_first += 1 # 흰색이 아닐 때 1을 더하여 색칠
                else:
                    if board[a][b] != 'W':
                        black_first += 1
                    if board[a][b] != 'B':
                        white_first += 1
        result.append(black_first)
        result.append(white_first)
print(min(result))

 

이번 문제는 유독 어려웠던 것 같다.

실버 4로 어려운 문제는 아닌데, 해결방법이 잘 떠오르지 않았던 문제이다. (타 블로그를 통해 해결방법을 배우고 작성한 코드입니다)

 

본 문제는 브루트포스 문제이다. 브루트포스에 대한 설명은 하단에 작성하도록 하겠습니다.

 

이중 for문으로 8*8의 체스판을 설정해준다 (N-7/M-7)

이후 흰색으로 시작한 경우에는 검은색으로 시작한 경우의 값을 초기화해준 뒤,

a와 b를 통해 8*8 체스판의 처음부터 검사를 한다.

(a+b)%2 == 0 는 행과 열의 인덱스 합이 짝수인 경우는 일정한 한 색을 가지게 되고,

인덱스의 합이 홀수인 경우에도 다른 일정한 한 색을 가지기 때문에 이렇게 작성하였다.  (아래의 그림을 통해 이해할 수 있다)

인덱스의 합이 짝수/홀수인지로 체크무늬를 판단할 수 있다. 

 

 

 

---

브루트포스란 ? (BruteForce)
검색 대상이 되는 원본 문자열의 처음부터 끝까지 차례대로 순회하며, 일일이 비교하는 방식의 알고리즘이다. 비교하고자 하는 문자열과 패턴을 한 칸씩 이동하면서 비교하여, 일치 여부를 확인한다.

 

 

브루트포스 비교 과정은 다음과 같다.

T: 원본 문자열, P: 찾고자 하는 문자열 

 

1. T, P 모두 첫 문자부터 비교를 시작하므로, 검색 인덱스를 맨 처음 인덱스로 설정한다.

2. 각각의 검색 인덱스부터 하나씩 문자를 비교한다.

• 비교 문자가 같으면 T, P의 인덱스 모두 옆으로 한 칸씩 이동한다.
• 비교 문자가 다르면 T의 인덱스는 한 칸 옆으로 이동하고, P의 인덱스는 맨 처음 인덱스로 돌아간다.

3. 2번 과정을 검색이 끝날 때까지 반복한다.

 

 

브루트포스의 시간복잡도와 장단점 

• 시간복잡도: O(mn) → 찾으려는 문자열 패턴의 길이: m, 총 문자열 길이: n
• 장점: 구현이 쉬운 편이다.
• 단점: 모든 자료를 탄색하므로 시간이 매우 비효율적이다.