[BOJ - JAVA] 15664 - N과 M 10(백트래킹)

# 주소

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

15664번: N과 M (10)

 

# 문제

 

# 문제 해설 및 코드 리뷰

import java.io.*;
import java.util.*;

public class Main {
	public static int[] arr,ans;
	public static int N, M;
	public static boolean[] visit;
    public static StringBuilder sb = new StringBuilder();
    public static LinkedHashSet<String> set;
	public static void main(String[] args) throws IOException{
        
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		arr = new int[M];
		ans = new int[N];
		set = new LinkedHashSet<>();
		st = new StringTokenizer(br.readLine());
        visit = new boolean[N];
        
        for(int i = 0; i < N; i++) {
        	ans[i] = Integer.parseInt(st.nextToken());
        }
        
        Arrays.sort(ans);
		dfs(0, 0);
		set.forEach(System.out::println);
	}
 
	public static void dfs(int depth, int t) {
		if (depth == M) {
			StringBuilder sb = new StringBuilder();
			for (int val : arr) {
				sb.append(val + " ");
			}
			set.add(sb.toString());
			sb.append('\n');
			return;
		}
		for(int i = t; i < N; i++) {
			if(!visit[i]) {
				visit[i] = true;
				arr[depth] = ans[i];
				dfs(depth+1, i+1);
				visit[i] = false;
			}
		}
	}
}

 

참 간단한 문제입니다. 정답률 80% 인데는 이유가 있는 것 같습니다. 이전 문제에 이어서 경우의 수를 비내림차순이 되게끔 출력하면 되겠습니다. 따라서 제일 밑의 for문의 i = t부터 시작하여 dfs의 depth와 i랑 각각 +1씩 해주면 계속해서 증가된 원소의 배열값을 얻을 수 있겠습니다. 

 

이전 리뷰에 근본적인 원리가 들어가 있으니 참고해주시길 바랍니다.

https://codingrapper.tistory.com/21

15663 - N과 M 9(백트래킹)