[백준] 15649번: N과 M (1) (dfs, 백트래킹)

https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

코드

import java.util.Scanner;

public class Main {
	static int arr[];
	static boolean visit[];
	static int N;
	static int M;
	static StringBuilder sb = new StringBuilder();
	
	public static void dfs(int count) {
		// dfs 함수 탈출 - 뽑은 갯수와 M이 동일할 때
		if(count == M) {
			// StringBuilder 에 뽑은 값(arr) 저장
			for(int i : arr)	
				sb.append(i + " ");
			sb.append("\n");
			return;
		}
		
		// 뽑지않은것 -> dfs 재귀호출
		for(int i=1; i<=N; i++) {
			if(!visit[i]) {
				visit[i] = true;	// 방문 체크
				arr[count] = i;		// 뽑기
				dfs(count+1);		// 그 다음 값 뽑기위해 재귀호출
				visit[i] = false;	// 뽑은 뒤 미방문 처리
			}
		}
	}

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		N = scan.nextInt();
		M = scan.nextInt();
		arr = new int[M];
		visit = new boolean[N+1];
		dfs(0);
		System.out.print(sb);
		scan.close();
	}

}

풀이

순열과 조합의 첫번째문제, 

dfs를 통해 깊숙히 방문하지 않은 곳을 뽑고, 뽑은갯수가 M과 동일할 때(dfs 탈출)

StringBuilder 에 넣어준다.