TIL 07-21 보호 필름

문제 정보

• 문제 이름: [SWEA 2112] 보호 필름
• 문제 링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V1SYKAaUDFAWU
• 알고리즘 분류: 백트래킹 (Backtracking), 브루트포스 (Brute Force), 완전 탐색

풀이 과정

1. 문제 분석 및 제약 조건 확인

• 문제 요약:
  두께 $D$, 가로 $W$ 크기의 단면을 가진 보호 필름이 주어진다. 각 셀은 A(0) 또는 B(1)의 특성을 가진다.
  모든 세로열(가로 $W$개의 각 열)에 대해 동일한 특성의 셀이 연속으로 $K$개 이상 존재하는지 검사하는 "성능 검사"를 통과해야 한다.
  검사를 통과하지 못할 경우, 특정 행 전체를 A(0) 또는 B(1)로 바꾸는 "약품 투약"을 진행한다. 성능 검사를 통과하기 위한 최소 약품 투약 횟수를 구해야 한다.

• 제약 조건 및 특이사항:

  • 보호 필름의 두께 $D$는 $3 \le D \le 13$로 비교적 작다.
  • 가로 크기 $W$는 $2 \le W \le 20$.
  • 합격 기준 $K$는 $1 \le K \le D$.
  • 약품을 칠할 수 있는 최악의 횟수는 $K$번이다. ($K$개의 연속된 행에 모두 같은 약품을 칠하면 무조건 통과하기 때문)

---

2. 알고리즘 및 자료구조 선택

• 반복적 깊이 증가 DFS (Iterative Deepening DFS / 백트래킹):
  최소 투약 횟수를 구해야 하므로, 투약 횟수의 제한(limit)을 $1$부터 $K$까지 $1$씩 늘려가며 탐색하는 방식을 선택했다.
  이 방식을 사용하면 가장 먼저 검사를 통과하는 순간의 limit 값이 곧 최소 투약 횟수가 되므로, 이후 더 깊은 탐색을 진행하지 않고 즉시 종료할 수 있다.

• 격자 데이터 관리:
  2차원 리스트(grid)로 필름 상태를 관리하며, 백트래킹 시 원본 행의 데이터를 복원하기 위해 1차원 리스트 슬라이싱(grid[y][:])을 활용한다.

---

3. 절차적 구현 흐름

1. 기초 상태 검사:

   • $K = 1$이거나, 약품을 전혀 투약하지 않은 원본 상태에서 check()를 통과하면 $0$을 출력하고 종료한다.

2. 투약 한도(limit) 설정 및 DFS 실행:

   • limit을 $1$부터 $K$까지 증가시키는 반복문을 실행한다.
   • 각 limit에 대해 dfs(y_index, cnt, limit)를 호출한다.

3. DFS 상태 탐색 및 분기 (백트래킹):

   • 기저 조건:
     • 이미 정답을 찾았다면(passed == True) 즉시 탐색 종료.
     • 현재 투약 횟수(cnt)가 목표한 limit에 도달하면 check()로 성능 검사를 실시한다. 성공 시 passed = True 설정 후 종료.
     • 필름의 끝 행에 도달했다면(y_index == D) 종료.
   • 3가지 탐색 분기:
     • 분기 1: 현재 행에 약품을 투약하지 않고 다음 행으로 이동 (dfs(y_index + 1, cnt, limit))
     • 분기 2: 현재 행을 $0$(A)으로 전체 투약 후 다음 행으로 이동
     • 분기 3: 현재 행을 $1$(B)로 전체 투약 후 다음 행으로 이동
   • 원상복구: 탐색 후에는 복사해 둔 원본 행(origin_row)으로 grid[y_index]를 복원한다.

4. 성능 검사 (check 함수):

   • 모든 열($x = 0 \dots W-1$)에 대해 아래에서 위로(또는 위에서 아래로) 연속된 동일 특성의 셀 개수(cnt)를 세어 $K$개 이상이 되는지 확인한다.
   • 단 하나의 열이라도 조건($K$개 연속)을 만족하지 못하면 즉시 False를 반환하고, 모든 열이 통과하면 True를 반환한다.

---

4. 시간 복잡도

• 최악의 상태 공간:
  행마다 선택할 수 있는 경우는 3가지(투약 안함, 0 투약, 1 투약)이다.
  두께 $D$에 대하여 $D$개의 행을 탐색할 때의 단순 완전 탐색 복잡도는 $O(3^D)$이다.

• 가지치기 및 백트래킹 적용:
  본 풀이에서는 limit을 $1$부터 올려가며 탐색하므로, 실제 탐색하는 상태의 수는 $\sum_{c=0}^{\text{ans}} \binom{D}{c} \cdot 2^c$에 해당한다.
  여기서 $D \le 13$이므로 최대 상태 수는 매우 작아진다.

• 성능 검사 비용:
  check() 함수 실행 시 $O(D \times W)$의 시간이 소요된다. ($13 \times 20 = 260$ 연산)

• 최종 시간 복잡도:
  최악의 경우에도 약 $O(3^D \times D \times W)$ 이하로 동작하며, 가지치기와 백트래킹 덕분에 제한 시간(3초) 내에 매우 여유롭게 통과한다.

5. 제출 코드

def check():
    for x in range(W):
        cnt = 1
        passed = False
        for y in range(1, D):
            if grid[y-1][x] == grid[y][x]:
                cnt += 1
                if cnt == K:
                    passed = True
                    break
            else:
                cnt = 1
        if not passed:
            return False
    return True


def dfs(y_index, cnt, limit):
    global passed
    
    # 검수 기준 통과 시 종료
    if passed:
        return
    
    # 정해놓은 한도에 색칠 횟수가 도달 했을 때 check하고 합격 시 종료
    if cnt == limit:
        if check():
            passed = True
        return
        
    # 검수에 합격하지 못한 채로 y 인덱스의 끝까지 도달했을 때 종료(실패)
    if y_index == D:
        return
    
    # 3가지 분기
    
    # 1. 그냥 다음 진행
    dfs(y_index+1, cnt, limit)
    
    # 2. 0으로 색칠
    origin_row = grid[y_index][:]
    grid[y_index] = [0] * W
    dfs(y_index+1, cnt+1, limit)
    
    # 3. 1로 색칠
    grid[y_index] = [1] * W
    dfs(y_index+1, cnt+1, limit)
    
    # 원상복구
    grid[y_index] = origin_row

T = int(input())
for tc in range(1, T+1):
    D, W, K = map(int, input().split())     # D는 두께 (y좌표), W는 가로 크기(x좌표), K는 검수 기준
    grid = [list(map(int, input().split())) for _ in range(D)]
    
    if K == 1 or check():
        print(f"#{tc} {0}")
        continue
    
    passed = False
    
    for i in range(1, K+1):
        dfs(0, 0, i)
        if passed:
            print(f"#{tc} {i}")
            break