[JAVA] 알고리즘 문제풀이 - DFS, BFS 기출문제 (조합 구하기)

DFS, BFS 기출문제 풀이

조합 구하기

• 설명 : 1부터 N까지 번호가 적힌 구슬이 있습니다. 이 중 M개를 뽑는 방법의 수를 출력하는 프로그램을 작성하세요.
  
  

• 입력 : 첫 번째 줄에 자연수 N(3<=N<=10)과 M(2<=M<=N)이 주어집니다.
  
  

• 출력 : 첫 번째 줄에 결과를 출력합니다. 출력 순서는 사전순으로 오름차순으로 출력합니다.
  
  

• 풀이 답안

import java.util.*;

public class Main {

    static int ball, sel;
    static int[] chk, result;

    public void solution(int idx, int num) {

        if(idx>sel) return;
        if(idx==sel) {
            for (int i : result) {
                System.out.print(i+" ");
            }
            System.out.println();
        } else {
            for(int i=num; i<=ball; i++){
                result[idx] = i;
                solution(idx+1, i+1);
            }

        }
    }

    public static void main(String[] args) {

        Main main = new Main();
        Scanner scan = new Scanner(System.in);
        ball = scan.nextInt();
        sel = scan.nextInt();
        chk = new int[ball+1];
        result = new int[sel];

        main.solution(0, 1);
    }
}

• 정리
  
  • 이전과 다르게 매개변수로 레벨과 시작값을 넣어주었다
    
  • 체크 변수로 풀이하는게 아니라 다음 수를 시작수부터~공의수까지 반복을 돌게하기 위함
    
  • 만약 공이 5이고 초기 매개변수가 0,1이라면 0레벨(결과의 첫번째공)에 1부터~5까지 차례로 가게하는것
    
  • 이때 재귀함수에는 2,i를 넣어주면서 2번째 자리에는 첫번째에 뽑은 공 이후의 수만 적용되게 함으로서 반복될수없게함
    
  • 레벨이 마지막에 도달한 경우에만 내용 출력