[Java] 완전탐색 4가지 케이스 (백준 N과 M)

 

 완전탐색 4대 패턴 정리

 

---

 

(1) 순열 (Permutation) – 방문 체크 필요

 

• 문제: N과 M (1) (15649)
• 순서 O, 중복 X
• 핵심: visited 배열로 사용 여부 체크

static void dfs(int depth) {
    if (depth == m) {
        for (int i = 0; i < m; i++) out.append(pick[i]).append(' ');
        out.append('\n');
        return;
    }

    for (int i = 1; i <= n; i++) {
        if (visited[i]) continue;  // 이미 사용된 숫자면 skip
        visited[i] = true;
        pick[depth] = i;
        dfs(depth + 1);
        visited[i] = false;       // 백트래킹
    }
}

 

---

 

(2) 조합 (Combination) – 시작점 이동

 

• 문제: N과 M (2) (15650)
• 순서 X, 중복 X
• 핵심: for (int i = start; …) 구조

static void dfs(int depth, int start) {
    if (depth == m) {
        for (int i = 0; i < m; i++) out.append(pick[i]).append(' ');
        out.append('\n');
        return;
    }

    for (int i = start; i <= n; i++) {
        pick[depth] = i;
        dfs(depth + 1, i + 1);  // 다음 숫자는 i+1부터
    }
}

 

---

 

(3) 중복 순열 (Permutation with Repetition)

 

• 문제: N과 M (3) (15651)
• 순서 O, 중복 O
• 핵심: visited 불필요

static void dfs(int depth) {
    if (depth == m) {
        for (int i = 0; i < m; i++) out.append(pick[i]).append(' ');
        out.append('\n');
        return;
    }

    for (int i = 1; i <= n; i++) {
        pick[depth] = i;
        dfs(depth + 1);  // 중복 허용하므로 방문 체크 없음
    }
}

 

---

 

(4) 중복 조합 (Combination with Repetition)

 

• 문제: N과 M (4) (15652)
• 순서 X, 중복 O
• 핵심: start 유지 (자기 자신 포함 가능)

static void dfs(int depth, int start) {
    if (depth == m) {
        for (int i = 0; i < m; i++) out.append(pick[i]).append(' ');
        out.append('\n');
        return;
    }

    for (int i = start; i <= n; i++) {
        pick[depth] = i;
        dfs(depth + 1, i);  // 자기 자신 포함 가능 → i 그대로
    }
}

 

---

 

포인트

• 순열: visited O
• 조합: start O
• 중복 순열: visited X, start X
• 중복 조합: visited X, start O (자기 자신 포함)