[BOJ - JAVA] 15655 - N과 M 6 (백트래킹)

# 주소

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

15655번: N과 M (6)

 

# 문제

 

# 문제 해설 및 코드 리뷰

public class Main {
    public static boolean[] visit;
	public static int[] arr;
	public static int N, M;
	public static int[] ans;

    public static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) {
        
		Scanner in = new Scanner(System.in);
 
		N = in.nextInt();
		M = in.nextInt();
		arr = new int[M];
        ans = new int[N];
        visit = new boolean[N];
        
        for(int i = 0; i < N; i++) {
        	ans[i] = in.nextInt();
        }
        Arrays.sort(ans);
		dfs(0,0);
        System.out.print(sb);
	}
 
	public static void dfs(int t,int depth) {
		if (depth == M) {
			for (int val : arr) {
                
				sb.append(val + " ");
			}	
			sb.append('\n');
			return;
		}
        
		for (int i = t ; i < N; i++) {
			if(!visit[i]) {
				visit[i] = true;
				arr[depth] = ans[i];
				dfs(i+1,depth + 1);
				visit[i] = false;
			}
		}
	}
}

이전 문제와 다른 점은 경우의 수가 늘 오름차순이어야 하고 중복을 허용하지 않게끔 출력해야 합니다. 따라서 이전 문제와 동일하게 visit[]이라는 boolean 타입의 배열을 생성하여 visit[i]에 방문할 때마다 true로 만들고 dfs 재귀함수를 실행한 뒤 visit[i]의 값을 false로 변경해주는 전형적인 백트래킹 방식을 채택했습니다.

그리고 받아온 ans값을 arr에 삽입시켜주면서 dfs의 i값과 depth 값을 각각 +1씩 증가시켜주어야 합니다. 이유는 depth값이 M과 같아질 때 마다 출력해야 하기 때문입니다. 그리고 i의 값을 +1씩 증가시켜 줄 때마다 그 다음 항의 배열의 값은 이전 항보다 증가된 값을 삽입할 수 있습니다. 

이것은 for문에 의한 i값의 증가가 아닌, dfs 재귀함수의 i값 증가로 인한 배열 출력입니다.