[Algorithm/Java] 알고리즘 자바 조합 구하기 DFS (코딩테스트, DFS, BFS, 조합, combination)

---

1. 문제 설명

• 설명
  1부터 N까지 번호가 적힌 구슬이 있습니다.
  이 중 M개를 뽑는 방법의 수를 출력하는 프로그램을 작성하세요.
• 입력
  첫째 줄에 자연수 N(3<=N<=10)과 M(2<=M<=N)이 주어집니다.
• 출력
  첫 번째 줄에 결과를 출력합니다.
  출력순서는 사전순으로 오름차순으로 출력합니다.

 

 

2. 문제 코드 및 풀이 설명

import java.util.Scanner;

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

  public static void main(String[] args) {
    Combination T = new Combination();
    Scanner kb = new Scanner(System.in);

    n = kb.nextInt();
    m = kb.nextInt();
    combi = new int[m];
    T.DFS(0, 1);
  }

  // 조합을 구하는 알고리즘
  // 제일 앞에서부터 하나씩 선택하며 순서를 고려하지 않으므로 다음 숫자는 뒤에 있는 숫자만 선택
  // 하나 선택 후 뒤에 것 중에 고르는 방식으로 재귀함수 호출
  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); // 입력된 수 다음 수부터 하나씩 선택하도록 호출
      }
    }
  }
}

 

3. 출력 예시

입력
4 2 

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

 

 

---

위의 내용은 인프런에서 수강할 수 있는 김태원님의 자바 알고리즘 문제풀이 강의를 바탕으로 공부한 내용을 정리한 내용입니다!

https://inf.run/iAi6

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