섹션 8. DFS, BFS 활용 - 9. 조합 구하기

문제 설명

1부터 N까지의 자연수 중에서 M개를 중복 없이 골라 오름차순 조합을 모두 출력하는 문제입니다.

입력 & 출력

입력

• 첫 번째 줄에 자연수 N(3 ≤ N ≤ 10), M(2 ≤ M ≤ N) 이 주어집니다.

출력

• 한 줄에 하나씩, 오름차순으로 조합을 출력합니다.

예시

입력:
4 2

출력:
1 2
1 3
1 4
2 3
2 4
3 4

해결 방법

• DFS와 백트래킹을 이용해서 조합을 탐색합니다.
• 오름차순으로 중복되지 않게 선택하기 위해 DFS(L, S)에서 S를 다음 단계로 넘겨줍니다.
• 종료 조건은 뽑은 숫자의 개수(L)가 M이 되었을 때입니다.

코드 구현

package partDfsBfs;

import java.util.Scanner;

public class Problem9 {
    static int n, m;
    static int[] combi;

    public void DFS(int L, int S) {
        if (L == m) {
            for (int x : combi) System.out.print(x + " ");
            System.out.println();
        } else {
            for (int i = S; i <= n; i++) {
                combi[L] = i;
                DFS(L + 1, i + 1);
            }
        }
    }

    public static void main(String[] args) {
        Problem9 T = new Problem9();
        Scanner kb = new Scanner(System.in);
        n = kb.nextInt();
        m = kb.nextInt();
        combi = new int[m];
        T.DFS(0, 1);
        kb.close();
    }
}

코드 설명

• DFS(int L, int S)
  • L: 현재까지 뽑은 숫자의 개수
  • S: 뽑기 시작할 숫자 (이전 숫자보다 큰 수부터 시작)
• combi[L] = i로 현재 숫자를 저장하고, 다음 깊이로 넘어가며 i+1부터 뽑게 해서 중복 방지

시간 복잡도 분석

• 조합의 수는 O(nCm)
• 최악의 경우 N=10, M=5일 때 252개의 조합을 출력하므로 충분히 빠르게 동작

---

출처: 인프런 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

https://www.inflearn.com/course/자바-알고리즘-문제풀이-코테대비/dashboard

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 강의 | 김태원 - 인프런