[BOJ - JAVA] 15666 - N과 M 12(백트래킹)

# 주소

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

15666번: N과 M (12)

 

# 문제

 

# 문제 해설 및 코드 리뷰

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];
		st = new StringTokenizer(br.readLine());
        set = new LinkedHashSet<>();
        for(int i = 0; i < N; i++) {
        	ans[i] = Integer.parseInt(st.nextToken());
        }
        
        Arrays.sort(ans);
		dfs(0, 0);
		StringBuilder sb2 = new StringBuilder();
		set.stream().forEach(i -> sb2.append(i + '\n'));
		System.out.println(sb2);
	}
 
	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++) {
				arr[depth] = ans[i];
				dfs(depth+1, i);
		}
	}
}

 

이전 문제와 동일하게 여러 숫자를 입력 받아, 그 숫자들을 LinkedHashSet에 입력 받아, 오름차순으로 정렬하였습니다. 당연히 입력받은 배열 간 중복은 허용되지 않기 때문에 LinkedHashSet을 이용했습니다.

문제 출력 조건이 같은 숫자를 여러번 사용할 수도 있고 비내림차순으로 정렬하게끔 유도하였으므로 for문에서 조금 건드려주도록 하겠습니다. 비내림차순일 때는 당연히 기존의 t값보다 더 커야 하기 때문에 i = t부터 시작하여 ans[i]값들을 arr에 삽입시켜줍니다. 그리고 dfs의 depth를 한차례씩 증가시키고 i값은 for문에서 증가하기 때문에 증가시키지 않습니다.(i+1을 시켜주면 i가 두번 증가될 수도 있으므로)

이 문제가 N과 M시리즈의 대망의 마지막 문제였습니다. 대부분 문제들이 기본에 충실하게 나와서 크게 어려운 것은 없었지만 이번에 문제를 풀면서 DFS를 처음 접하였기 때문에 처음 이해하는 데에 난해한 부분이 없잖아 있었습니다. 하지만 12번째 시리즈의 문제에 도달할 때 쯤 관련된 비슷한 문제는 어느정도 DFS로 사고할 수 있게 된 것 같아 기쁩니다.

여러분들도 저처럼 도움이 많이 되었으면 좋겠습니다. 감사합니다.