"

수업 목표

본 수업은 모든 가능성을 빠짐없이 탐색하는 완전 탐색의 핵심 기법을 이해하고, 이를 효율적으로 확장하는 백트래킹과 비트마스크 기법을 습득하는 것을 목표로 합니다. - 완전 탐색의 개념을 파악하고 상태 공간 트리를 설계하여 가능한 모든 경우의 수를 구합니다. - 가망이 없는 분기점을 판단하고 조기에 탐색을 중단하는 강력한 가지치기 기법을 적용합니다. - 비트 연산의 기본 원리를 익히고 비트마스크를 활용해 방문 여부나 선택 상태를 압축하여 연산 속도를 극대화합니다. - 의존성이 있는 작업 순서에서 탐욕적 기법과 위상 정렬을 결합하여 교체 비용을 최적화하는 시뮬레이션을 구현합니다.

학습 동기부여

알고리즘 설계에서 가장 직관적이면서 확실한 정답률을 보장하는 접근법은 바로 모든 경우의 수를 확인하는 것입니다. 그러나 후보의 수가 조금만 늘어나도 단순 탐색은 시간 초과를 마주하게 됩니다. 이때 가망이 없는 경로를 조기에 포기하고 되돌아가는 백트래킹과 가지치기를 결합하면, 수천만 년이 걸릴 탐색을 단 몇 밀리초 만에 해결할 수 있습니다. 특히 파이썬에서 1바이트 크기의 정수를 사용해 32개 이상의 상태 정보를 단 한 번의 비트 연산으로 판정하는 비트마스크 기법은 시간과 메모리 모두를 비약적으로 아껴주는 핵심 최적화 도구입니다.

도입 스토리

미로 찾기를 진행할 때 막다른 길에 다다르면 직전 갈림길로 되돌아가 다른 방향을 시도하게 됩니다. 이것이 백트래킹의 핵심입니다. 만약 갈림길 입구에 이 방향은 출구와 연결되지 않는다는 단서가 적혀 있다면, 우리는 그 미로 전체를 탐색할 필요 없이 바로 다음 갈림길로 넘어갈 수 있습니다. 이것이 바로 가지치기입니다. 더불어 내가 방문했던 갈림길 번호들을 종이 한 장에 체크 표시하는 대신, 스위치 켜고 끄기처럼 비트 신호 하나로 매우 빠르게 기록하고 읽어낼 수 있다면 탐색 시간은 극적으로 단축될 것입니다. 본 수업에서는 이러한 완전 탐색의 심화 최적화 기법들을 실제 코드로 구현해 봅니다.

1. 완전 탐색과 재귀 백트래킹

완전 탐색은 가능한 모든 해를 탐색하는 방법입니다. $N$개의 원소 중 부분집합을 선택하는 경우의 수는 $2^N$이며, 순열을 만드는 경우의 수는 $N!$입니다. 재귀 함수를 이용해 각 단계에서 선택을 내리고, 호출이 종료되면 상태를 복구하며 다음 선택으로 넘어가는 백트래킹 구조를 만듭니다.

# 8007번: 사과 분할 — 비트마스크를 활용한 2^N 완전 탐색
import sys
input = sys.stdin.readline

n = int(input())
p = list(map(int, input().split()))
total_sum = sum(p)
min_diff = total_sum

# 2^n 가지 부분집합의 모든 무게 합을 구하여 최소 차이 계산
for i in range(1 << n):
    curr_sum = 0
    for j in range(n):
        if (i >> j) & 1:
            curr_sum += p[j]
    diff = abs(total_sum - 2 * curr_sum)
    if diff < min_diff:
        min_diff = diff

print(min_diff)

2. N-Queens와 대각선 점유 체크 최적화

체스판에 서로 공격할 수 없도록 퀸을 배치할 때, 행을 기준으로 한 칸씩 내려가며 열과 대각선 점유 여부를 검사합니다. 열 점유 배열, 우상향 대각선 점유 배열, 우하향 대각선 점유 배열을 관리하여 $O(1)$ 시간에 충돌 여부를 검사합니다.

# 8008번: 체스판과 퀸 — 백트래킹 검사 배열 적용
import sys
input = sys.stdin.readline

board = [input().strip() for _ in range(8)]
cols = [False] * 8
diag1 = [False] * 15  # r + c 가 같으면 같은 우상향 대각선
diag2 = [False] * 15  # r - c + 7 이 같으면 같은 우하향 대각선
ans = 0

def backtrack(r):
    global ans
    if r == 8:
        ans += 1
        return
    for c in range(8):
        if board[r][c] == '*':
            continue
        if cols[c] or diag1[r+c] or diag2[r-c+7]:
            continue
        
        # 상태 기록 후 진입
        cols[c] = diag1[r+c] = diag2[r-c+7] = True
        backtrack(r + 1)
        # 상태 복구 (Backtrack)
        cols[c] = diag1[r+c] = diag2[r-c+7] = False

backtrack(0)
print(ans)

3. 격자 경로 탐색과 가지치기

모든 격자점을 정확히 한 번 지나 도달해야 하는 해밀턴 경로 탐색은 단순 DFS로 해결할 수 없습니다. 두 가지 강력한 가지치기가 필수적입니다. - 현재 위치에서 도달해야 할 최종 목적지까지의 맨해튼 거리가 남은 남은 이동 횟수보다 크면 탐색을 중단합니다. - 앞으로 나아가려고 할 때 정면은 벽이거나 이미 방문한 칸인데, 좌우가 모두 비어 있는 경우 격자가 양쪽 영역으로 쪼개져 고립 지역이 생기므로 즉시 중단을 선언합니다.

# 8009번: 격자 경로 — 고립 영역 분할 감지 가지치기 구조
def dfs(r, c, step):
    global ans
    if r == 7 and c == 1:
        if step == 48:
            ans += 1
        return
    if step == 48:
        return
    
    # 가지치기 1: 남은 맨해튼 거리 검사
    if abs(7 - r) + abs(1 - c) > (48 - step):
        return
        
    # 가지치기 2: 상하좌우 고립 영역 분할 검사
    up = visited[r-1][c]
    down = visited[r+1][c]
    left = visited[r][c-1]
    right = visited[r][c+1]
    
    if up and down and not left and not right:
        return
    if left and right and not up and not down:
        return
        
    visited[r][c] = True
    req_dir = steps[step]
    if req_dir != -1:
        nr, nc = r + dr[req_dir], c + dc[req_dir]
        if not visited[nr][nc]:
            dfs(nr, nc, step + 1)
    else:
        for d in range(4):
            nr, nc = r + dr[d], c + dc[d]
            if not visited[nr][nc]:
                dfs(nr, nc, step + 1)
    visited[r][c] = False

4. 위상 정렬과 탐욕적 디스크 교체 시뮬레이션

의존 관계가 있는 패키지들을 두 개의 디스크로 분리하여 설치할 때, 각 디스크별로 설치 가능한 목록을 큐로 분리하여 관리합니다. 현재 선택된 디스크의 설치 가능 목록이 고갈될 때까지 패키지를 꺼내어 설치하며 의존성을 해제하고, 설치 가능한 패키지가 다른 디스크에만 존재할 때 드라이브를 교체합니다.

# 8010번: 모든 디스크 선택 — 디스크 스위칭 위상 정렬 시뮬레이션
def simulate(start_disk):
    deg = list(in_degree)
    q1 = []
    q2 = []
    
    for i in range(1, n + 1):
        if deg[i] == 0:
            if i <= n1:
                q1.append(i)
            else:
                q2.append(i)
                
    curr_disk = start_disk
    switches = 0
    
    while q1 or q2:
        if curr_disk == 1:
            if not q1:
                curr_disk = 2
                switches += 1
                continue
            curr = q1.pop()
            for nxt in adj[curr]:
                deg[nxt] -= 1
                if deg[nxt] == 0:
                    if nxt <= n1:
                        q1.append(nxt)
                    else:
                        q2.append(nxt)
        else:
            if not q2:
                curr_disk = 1
                switches += 1
                continue
            curr = q2.pop()
            for nxt in adj[curr]:
                deg[nxt] -= 1
                if deg[nxt] == 0:
                    if nxt <= n1:
                        q1.append(nxt)
                    else:
                        q2.append(nxt)
    return switches + 1

자주 하는 실수 & 오류 예방

- 재귀 호출 시 과도한 상태 복사: 매 단계마다 방문 배열을 복사하여 넘겨주면 메모리 할당 및 복사 작업으로 인해 무조건 시간 초과가 발생합니다. 전역 방문 배열을 선언하고 재귀 호출 전 방문 표시를 작성한 뒤, 호출이 리턴되면 즉시 방문 표시를 해제하는 원복 구조를 취해야 합니다. - 비트 연산자 우선순위 혼동: 비트 연산자(&, |, << 등)는 비교 연산자(== 등)보다 순위가 낮습니다. 따라서 (mask & (1 << i)) != 0과 같이 반드시 괄호를 씌워 계산 순서를 수동으로 명시해야 합니다. - 재귀 제한 해제 누락: 파이썬은 기본 최대 재귀 깊이가 1000입니다. 격자 경로 탐색처럼 깊이가 48을 초과하는 복잡한 깊이 우선 탐색을 구현할 때는 코드 상단에 sys.setrecursionlimit(10000)을 명시해야 안정적으로 런타임 오류를 방지할 수 있습니다. - 인덱스 바운더리 체크 오류: 격자나 체스판 경계선 바깥을 탐색하지 않도록 경계 처리를 세심하게 작성하거나, 격자 외곽에 벽(True)을 한 칸씩 둘러주는 기법을 적용하면 계산 실수를 대폭 예방할 수 있습니다.

핵심 정리

개념	주요 기법	주요 최적화 포인트	대표 문제 유형
완전 탐색	재귀 호출, 반복문 조합	중복 상태 제거, 모든 상태 커버 보장	부분집합 생성, 순열 생성
백트래킹	상태 공간 트리, 되돌아가기	전역 배열을 통한 리스트 복사 차단 및 원복	N-Queens, 조합 탐색
가지치기	중간 유효성 판단	맨해튼 거리 측정, 영역 단절 조기 감지	격자 경로 탐색, 해밀턴 경로
비트마스크	비트 연산(AND, OR, XOR)	정수 하나에 여러 상태(True/False) 압축 및 연산	집합 표현, 상태 압축 DP
위상 정렬	진입 차수 관리 큐	디스크별 큐 분류를 통한 스위칭 최소화	의존성 작업 배치, 공정 설계

실습 문제

문제 번호	문제 제목	출처	난이도	핵심 알고리즘
8007	사과 분할	CSES	쉬움	비트마스크 부분집합 탐색
8008	체스판과 퀸	CSES	보통	대각선 점유 체크 백트래킹
8009	격자 경로	CSES	어려움	경로 단절 가지치기 DFS
8010	모든 디스크 선택	SPOJ	보통	위상 정렬 기반 스위칭 최적화