[BOJ] 15649: N과 M(1) (JAVA)

15649번: N과 M (1)

package 백준renew;

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

public class 실버3_15649_N과M_1 {
	static int N, M;
	static boolean visited[];
	static int arr[];
	static int count;
	static String number;
	static List<String> list = new ArrayList<>();
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		arr = new int[N];
		count = 1;
		number = "";
		
		for(int i=0; i<N; i++) {
			visited = new boolean[N];
			visited[i] = true;
			number = (i+1)+" ";
			DFS(i, count, number);
		}
		
		Collections.sort(list);
		
		for(int i=0; i<list.size(); i++) {
			String tmp = list.get(i);
			tmp = tmp.substring(0, tmp.length()-1);
			sb.append(tmp).append('\n');
		}
		
		System.out.println(sb.toString());
	}
	static void DFS(int i, int count, String number) {
		if(count == M) {
			list.add(number);
		}
		
		for(int j=0; j<N; j++) {
			if(i != j && !visited[j]) {
				visited[j] = true;
				DFS(j, count+1, number+(j+1)+" ");
				visited[j] = false;
			}
		}
	}
}

 

String으로 변환해서 list에 담아준 뒤, Collections.sort로 정렬한 다음 출력해주었다.

이보다 더 효율적으로 문제를 풀 수 있을 것 같은데 .. String으로 변환하지 않고도 출력할 수 있을 것 같은데 !

조금 더 백트래킹을 공부하면서 익숙해져야 할 것 같다 ㅜㅜ