728x90
반응형
- 문제
- 올바른 풀이
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
- 장점: 구현이 쉬운 편이다.
- 단점: 모든 자료를 탄색하므로 시간이 매우 비효율적이다.
728x90
'자료구조 및 알고리즘 > 백준' 카테고리의 다른 글
[python] 10845. 큐 (0) | 2023.01.27 |
---|---|
[python] 10828. 스택 (0) | 2023.01.27 |
[python] 1920. 수 찾기 (0) | 2023.01.26 |
[python] 1003. 피보나치 함수 (0) | 2023.01.21 |
[python] 18870. 좌표 압축 (0) | 2023.01.19 |