동블

그래프 뷰

02. 완전탐색-백트래킹

3 min read

완전탐색 / 백트래킹 / 비트마스크

Summary

N이 작고 모든 순서/선택을 봐야 하면 완전탐색부터 의심한다.
삼성/SWEA는 조합 + 시뮬레이션, 조합 + BFS가 자주 나온다.

선택 기준

상황추천
순서가 중요순열
순서가 중요하지 않음조합
선택/미선택부분집합
N ⇐ 20 집합 표현비트마스크
모든 경우지만 중간에 불가능 판단 가능백트래킹 + 가지치기

순열 / 조합 / 부분집합 검증 템플릿

import java.io.*;
import java.util.*;
 
public class Main {
    static int n, r;
    static int[] arr;
    static int[] selected;
    static boolean[] used;
    static long permutationCount;
    static long combinationCount;
    static long subsetCount;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        r = Integer.parseInt(st.nextToken());
 
        arr = new int[n];
        selected = new int[r];
        used = new boolean[n];
 
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
 
        perm(0);
        comb(0, 0);
        subset(0);
 
        System.out.println(permutationCount);
        System.out.println(combinationCount);
        System.out.println(subsetCount);
    }
 
    static void perm(int depth) {
        if (depth == r) {
            permutationCount++;
            return;
        }
 
        for (int i = 0; i < n; i++) {
            if (used[i]) continue;
 
            used[i] = true;
            selected[depth] = arr[i];
            perm(depth + 1);
            used[i] = false;
        }
    }
 
    static void comb(int start, int depth) {
        if (depth == r) {
            combinationCount++;
            return;
        }
 
        for (int i = start; i < n; i++) {
            selected[depth] = arr[i];
            comb(i + 1, depth + 1);
        }
    }
 
    static void subset(int idx) {
        if (idx == n) {
            subsetCount++;
            return;
        }
 
        subset(idx + 1); // 선택 안 함
        subset(idx + 1); // 선택함
    }
}

비트마스크 기본

for (int mask = 0; mask < (1 << n); mask++) {
    for (int i = 0; i < n; i++) {
        if ((mask & (1 << i)) != 0) {
            // i번째 원소 선택됨
        }
    }
}

주의점

실수주의
중복 원소 처리 없음값 기준 중복 제거가 필요한지 확인
가지치기 과함정답 후보를 잘라내지 않는지 확인
1 << NN >= 31이면 int overflow
R = 0빈 선택도 하나의 경우
R = N순열/조합 종료 조건 확인

백지 복원

1. 순열과 조합의 for문 시작점 차이는?
2. used[]가 필요한 유형은?
3. 부분집합 재귀에서 선택/미선택 호출 순서를 써라.
4. N <= 20이면 비트마스크를 떠올리는 이유는?

관련 문서