[백준] 15663 N과 M (9) - 백트래킹 JAVA

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

15663번: N과 M (9)

코드설명

백트래킹 문제입니다.

 

각 조합을 visited를 통해 한번만 각 숫자들을 호출하도록하고,

HashSet을 활용하여 중복된 수열은 걸러주었습니다.

여기서 시간이 잡아먹힌 부분은, Hashset과 StringBuilder를 활용할때 HashSet에 단순히 sb를 넣어서 틀렸었습니다.

HashSet값에 sb.toString() 처리릍 통하여 String형으로 변화시켜주어야합니다.

 

 

Hashset을 활용하지 않고, 수열을 정렬되었다는 상태를 활용하여 바로 이전의 before값을 설정하여 딱 한번만 호출하도록 하는 코드도 있었습니다.

수열이 정렬되었을때만 사용할 수 있는 방식이지만, 해당 방식도 좋아보여서 아래에 코드로 남겨두었습니다.

 

 

코드

HashSet을 활용한 코드

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

public class Main {
	public static int N, M;
	public static int[] arr;
	public static int[] answerArr;
	public static boolean[] visited;
	public static StringBuilder sb = new StringBuilder();
	public static HashSet<String> hashset = new HashSet<String>();
	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];
    	for(int i=0;i<N;i++) {
    		arr[i] = Integer.parseInt(st.nextToken());
    	}
    	Arrays.sort(arr);
    	answerArr = new int[M];
    	visited = new boolean[N];
    	simulate(0,0);
    	System.out.println(sb.toString());
    }
    
    public static void simulate(int idx, int level) {
    	if(level == M) {
    		StringBuilder sb1 = new StringBuilder();
    		for(int a : answerArr) {
    			sb1.append(a).append(" ");
    		}
    		
    		if(hashset.contains(sb1.toString()) == false) {
    			
        		for(int a : answerArr) {
        			sb.append(a).append(" ");
        		}
        		sb.append("\n");
        		hashset.add(sb1.toString());
    		}

    		return ;
    	}
    	
    	for(int i=0;i<N;i++) {
    		if(visited[i] == false) {
    			visited[i] = true; //이미 사용된 수열은 사용하지 않기 위한 처리입니다.
        		answerArr[level] = arr[i];
        		simulate(i, level + 1);
        		visited[i] = false;
    		}
    	}
    }
}

 

before 변수를 활용하여 바로 이전에 사용한 코드값을 저장해두면서 만약 이미 사용한 코드라면 사용하지 않습니다.

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

public class Main {
	public static int N, M;
	public static int[] arr;
	public static int[] answerArr;
	public static boolean[] visited;
	public static StringBuilder sb = new StringBuilder();
	public static HashSet<String> hashset = new HashSet<String>();
	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];
    	for(int i=0;i<N;i++) {
    		arr[i] = Integer.parseInt(st.nextToken());
    	}
    	Arrays.sort(arr);
    	answerArr = new int[M];
    	visited = new boolean[N];
    	simulate(0,0);
    	System.out.println(sb.toString());
    }
    
    public static void simulate(int idx, int level) {
    	if(level == M) {
    		
    		for(int a : answerArr) {
    			sb.append(a).append(" ");
    		}
    		sb.append("\n");
    		return ;
    	}
    	
    	int before = 0;
    	for(int i=0;i<N;i++) {
    		if(visited[i] == false) {
    			
    			if(before == arr[i]) continue;
    			
    			visited[i] = true; //이미 사용된 수열은 사용하지 않기 위한 처리입니다.
    			before = arr[i];
        		answerArr[level] = arr[i];
        		simulate(i, level + 1);
        		visited[i] = false;
    		}
    	}
    }
}