99클럽 코테 스터디 _ 11일차 TIL (브루트 포스)

 

< 문제 >

[백준] 1018. 체스판 다시 칠하기 / 실버4

---

< 풀이 >

코드 변수 정의

• function : check_pattern
  • pattern1, pattern2 : 체스판의 시작이 W인 패턴, 체스판의 시작이 B인 패턴
  • replace1 : pattern1인 체스판인 경우 다시 칠해야 하는 칸의 수
  • replace2 : pattern2인 체스판인 경우 다시 칠해야 하는 칸의 수
• function : f
  
  • compare_board : 주어진 보드에서 잘라낸 8X8 체스판
  • min_ans : 체스판에서 다시 칠해야 하는 정사각형의 최소 개수

---

Brute Force
시간복잡도 : O(NXM)

def check_pattern(board):
    pattern1 = ['WBWBWBWB', 'BWBWBWBW'] * 4  # 시작이 W인 패턴
    pattern2 = ['BWBWBWBW', 'WBWBWBWB'] * 4  # 시작이 B인 패턴
    
    # pattern1인 경우 다시 칠해야 하는 칸의 수
    replace1 = sum(board[i][j] != pattern1[i][j] for i in range(8) for j in range(8))
    # pattern2인 경우 다시 칠해야 하는 칸의 수
    replace2 = sum(board[i][j] != pattern2[i][j] for i in range(8) for j in range(8))
    
    # W, B로 시작하는 체스판 중 다시 칠하는 칸의 수가 더 적은 값을 반환한다.
    return min(replace1, replace2)

def f():
    N, M = map(int, input().split())
    board = [input().strip() for _ in range(N)]
    
    min_ans = float('inf') # 다시 칠해야 하는 정사각형의 최소 개수
    
    # 주어진 보드로 만들 수 있는 8X8 체스판의 모든 경우의 수
    for i in range(N - 7):
        for j in range(M - 7):
            compare_board = [board[x][j:j+8] for x in range(i, i+8)] # 8X8 체스판
            min_ans = min(min_ans, check_pattern(compare_board))
    
    return min_ans
    
print(f())

---

 

 

 

풀이 방식

1. check_pattern 함수 : 8X8 체스판의 색칠 변경 횟수 계산
   • 입력된 8X8 크기의 board를 두 가지 체스판 패턴과 비교하여 변경해야 하는 칸의 개수를 구한다.
   • pattern1 : 체스판이 'W'로 시작하는 경우의 올바른 패턴
     • WBWBWBWB
       BWBWBWBW
       WBWBWBWB
       BWBWBWBW
       WBWBWBWB
       BWBWBWBW
       WBWBWBWB
       BWBWBWBW
   • pattern2 : 체스판이 'B'로 시작하는 경우의 올바른 패턴
     • BWBWBWBW
       WBWBWBWB
       BWBWBWBW
       WBWBWBWB
       BWBWBWBW
       WBWBWBWB
       BWBWBWBW
       WBWBWBWB
   • replace1 : 현재 보드와 pattern1을 비교하여 다른 문자의 개수를 계산
   • replace2 : 현재 보드와 pattern2를 비교하여 다른 문자의 개수를 계산
   • min(replace1, replace2) : 두 개의 패턴 중 더 적은 변경 횟수를 반환한다.
2. f 함수 : 최소 수정 횟수 찾기
   • 주어진 NXM 보드에서 8X8 크기의 모든 부분 보드를 확인하여 최소 수정 횟수를 구한다.
   • board는 input값에 strip()을 사용하여 불필요한 공백을 제거한다.
   • 체스판은 8X8 크기여야 하므로, 시작 위치 (i, j)는 (N-7, M-7) 범위 내에서 선택한다.
     • 현재 (i, j) 위치에서 8X8 크기의 부분 보드를 추출한다.
     • board[i][j:j+8]를 통해 8개의 연속된 행을 가져온다.
   • check_pattern(compare_board)를 호출하여 현재 보드에서 최소 변경 횟수를 구하고 min_ans를 업데이트한다.

 

• 1.  

---

< 회고 >

브루트 포스(Brute Force)

브루트 포스는 가능한 모든 경우의 수를 직접 탐색하여 정답을 찾는 방법

 

 

특징

• 모든 경우의 수를 검사하기 때문에 정확한 정답을 보장한다.
• 구현이 간단하며, 직관적으로 이해하기 쉽다.
• 경우의 수가 많아지면 시간 복잡도가 증가하여 비효율적일 수 있다.
• 데이터의 크기가 작을 때 적절한 방법이다.

 

동작 방식

• 모든 가능한 조합을 생성한다.
• 각 경우를 검사하여 조건을 만족하는지 확인한다.
• 최적의 답을 선택한다.

 

예제

• 비밀번호 해킹 예제
  • 비밀번호가 4 자리(0000 ~ 9999)라면, 브루트 포스 방식으로 0000부터 9999까지 전부 시도하여 맞는 비밀번호를 찾을 수 있다.
  • 모든 조합을 시도하는 무식한 방법이지만 반드시 정답을 찾는다.
• 8 x 8 체스판 다시 칠하기 (위 문제)
  • 모든 가능한 위치에서 탐색하여 최적의 정답을 찾는 방법이다.
    1. 체스판을 자를 수 있는 모든 경우(부분 보드)를 탐색한다.
    2. 각 경우에서 다시 칠해야 하는 최소 횟수를 계산한다.
    3. 최소 횟수를 갱신하면서 정답을 찾는다.

 

시간 복잡도

• 일반적으로 가능한 모든 경우를 탐색하기 때문에 시간 복잡도가 크다는 단점이 있다.
  • n자리 비밀번호 찾기 : O(10^n)
  • n개의 원소로 만들 수 있는 모든 순열 : O(n!)
  • n x m 체스판에서 8 x 8 탐색 : O(NM)

 

개선 방법

• 백트래킹(Backtracking)   →    불필요한 경우의 수를 조기에 가지치기하여 탐색 속도를 향상한다.
• 가지치기(Pruning)            →    조건을 만족하지 않는 경우 더 깊이 탐색하지 않는다.
• 다이나믹 프로그래밍(DP)   →    중복 계산을 줄여 효율적으로 해결한다.
• 비트마스킹(Bitmasking)   →    브루트 포스를 빠르게 수행하는 기법이다.

 

브루트 포스를 사용하는 경우

• 가능한 경우의 수가 적을 때
• 확실한 정답을 찾고 싶을 때
• 문제를 더 효율적인 방법으로 해결하기 전 아이디어를 구상할 때