[BAEKJOON] 15650번 : N과 M(2) (JAVA)

- 알고리즘 분류 : DFS, 백트래킹

- 사용 언어 : JAVA

 

DFS와 백트래킹을 이용하여 조합을 구하는 문제입니다.

 

이전 게시글(N과 M(1))과 다른 부분은 호출한 함수에서 수를 선택할 때 현재 숫자에서 +1부터 시작한다는 부분입니다.

 

소스 설명은 주석을 참고해주세요.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static int N, M;
	
	public static boolean[] visited;
	
	// 조합 계산
	public static void calcCombi(int num, int count) {
		
		// 선택한 수가 M일 때 출력
		if(count >= M) {
			for(int i=0; i<N; i++) {
				// 고른(true로 설정한) 녀석만 출력
				if(visited[i]) {
					System.out.print((i+1) + " ");
				}
			}
			System.out.println();
			
			// 함수 종료
			return;
		}
		
		// 수 선택하기
		for(int i=num+1; i<N; i++) {
			// 선택하지 않은 수라면
			if(visited[i] == false) {
				
				// 선택
				visited[i] = true;
				calcCombi(i, count+1);
				
				// 선택 취소 (백트래킹)
				visited[i] = false;
			}
		}
	}
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		visited = new boolean[N];
		
		calcCombi(-1, 0);
		
	}

}