수업 목표 및 핵심 역량

- 모든 부분집합($2^N$)과 순열($N!$)을 누락 없이 생성합니다. - 대각선 점유 배열 및 $O(1)$ 판정 기법으로 N-Queens를 해결합니다. - 영역 분할 감지 기법을 설계하여 격자 경로 탐색 시간을 단축합니다. - 비트 연산을 활용해 메모리와 연산 효율을 높입니다. - 디스크별 진입 차수 큐를 다루어 교체 횟수를 최소화합니다.

완전 탐색과 재귀 백트래킹

- 가능한 모든 해를 빠짐없이 탐색하는 완역 구조 설계 - 호출이 끝나면 상태를 복구하며 다음 경로로 탐색

# 8007번: 사과 분할 (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)
    min_diff = min(min_diff, diff)

N-Queens 대각선 점유 판정

- 열 점유, 우상향 대각선($r+c$), 우하향 대각선($r-c+offset$)을 배열로 관리 - 배치 확인 및 롤백을 $O(1)$에 처리

# 8008번: 체스판과 퀸
def backtrack(r):
    if r == 8:
        return 1
    ans = 0
    for c in range(8):
        if board[r][c] == '*' or cols[c] or diag1[r+c] or diag2[r-c+7]:
            continue
        cols[c] = diag1[r+c] = diag2[r-c+7] = True
        ans += backtrack(r + 1)
        cols[c] = diag1[r+c] = diag2[r-c+7] = False
    return ans

격자 경로 탐색과 가지치기 (Pruning)

- 맨해튼 거리가 남은 이동 횟수보다 크면 중단 - 진행 방향 전면이 막히고 좌우가 비어 있으면 단절 영역 발생하므로 차단

# 8009번: 격자 경로 핵심 가지치기 조건
# 상하 막힘 & 좌우 뚫림 검출
if visited[r-1][c] and visited[r+1][c] and not visited[r][c-1] and not visited[r][c+1]:
    return
# 좌우 막힘 & 상하 뚫림 검출
if visited[r][c-1] and visited[r][c+1] and not visited[r-1][c] and not visited[r+1][c]:
    return

위상 정렬 기반 디스크 스위칭

- 각 디스크에 해당하는 설치 가능 목록을 전용 큐로 이원화 - 현재 장착한 디스크의 큐가 고갈될 때만 다른 디스크로 교체

# 8010번: 모든 디스크 선택 시뮬레이션 루프
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:
                q1.append(nxt) if nxt <= n1 else q2.append(nxt)
    # curr_disk == 2 인 경우도 대칭적으로 동일하게 진행

오류 예방 및 작성 요령

- **깊은 재귀 오류 방지**: 상단에 sys.setrecursionlimit() 지정 - **비트 연산 괄호 씌우기**: mask & 1 == 0 은 잘못된 계산 → (mask & 1) == 0 으로 명확히 작성 - **불필요한 리스트 복사 제거**: 상태를 새로 만들어 매번 함수의 인자로 전달하지 말고 전역 배열 및 백트랙 시 값 복구를 활용 - **경계 조건 미리 채우기**: 격자 외곽을 벽(True)으로 한 겹 감싸 경계선 검사 횟수 단축