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

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

15655번: N과 M (6)

코드설명

백트래킹(BackTracking)을 활용하는 문제입니다.

 

simulate 메서드 : 해당 함수는 현재까지 선택된 원소의 개수(level)와 다음에 선택할 원소의 인덱스(idx)를 인자로 받습니다.

이를 통해서 중복된 순열을 제거하고 출력할 수 있습니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	public static int N, M, K;
	public static int[] arr;
	public static int[] selected;
	public static boolean[] visited;
	public static int answer = 0;
    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());
    	
    	st = new StringTokenizer(br.readLine());
    	
    	arr = new int[N];
    	selected = new int[M];
    	visited = new boolean[N];
    	
    	for(int i=0;i<N;i++) {
    		arr[i] = Integer.parseInt(st.nextToken());
    	}
    	Arrays.sort(arr);
    	
    	simulate(0, 0);
    }
    
    public static void simulate(int level, int idx) {
    	if(level == M) {
    		for(int i=0;i<M;i++) {
    			System.out.print(selected[i]+" ");
    		}
    		System.out.println();
    		return ;
    	}
    	
    	for(int i=idx;i<N;i++) {
    		if(visited[i] == false) {
    			visited[i] = true;
    			selected[level] = arr[i];
    			simulate(level + 1, i+1);
    			visited[i] = false;
    		}
    		
    	}
    }
}