[백준] 5568 카드 놓기 - 완전탐색(DFS) JAVA

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

5568번: 카드 놓기

문제풀이

DFS로 모든 조합을 구한뒤, HashSet으로 중복되는 부분을 빼주면 됩니다.

 

DFS를 진행하며 신경쓸 점은 제출한 코드와 이 아래코드를 비교하면 됩니다.

제출한 코드는 idx가 존재하지 않아 모든 경로를 처음부터 다시 돕니다. 즉, 순열을 구합니다.

 

아래의 코드는 idx가 존재하여 한번 지나간 경로는 검사하지 않습니다. 즉, 조합을 구합니다.

DFS로 완전탐색을 통하여 경우의 수를 구할때는 해당 사항만 주의하면 될 것 같습니다.

public static void simulate(int idx, String s, int level){
    if(level == k) {
//    		System.out.println(s);
        hashset.add(s);
        return ;
    }
    for(int i=idx;i<n;i++) {
        if(visited[i] == true) continue;
        visited[i] = true;
        simulate( s + String.valueOf(card[i]), level + 1);
        visited[i] = false;
    }	
}

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {	
	public static int n, k;
	public static int[] card;
	public static boolean[] visited;
	public static HashSet<String> hashset = new HashSet<>();
    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()); // 아이스크림 종류
    	st = new StringTokenizer(br.readLine());
    	k = Integer.parseInt(st.nextToken()); // 섞어먹으면 안되는 조합의 개수
    
    	card = new int[n];
    	visited = new boolean[n];
    	
    	for(int i=0;i<n;i++) {
    		st = new StringTokenizer(br.readLine());
    		card[i] = Integer.parseInt(st.nextToken()); 
    	}
    	
    	simulate(new String(), 0);
    	System.out.println(hashset.size());
	}
    
    public static void simulate(String s, int level){
    	if(level == k) {
//    		System.out.println(s);
    		hashset.add(s);
    		return ;
    	}
    	for(int i=0;i<n;i++) {
    		if(visited[i] == true) continue;
    		visited[i] = true;
    		simulate( s + String.valueOf(card[i]), level + 1);
    		visited[i] = false;
    	}	
    }
}

 

코드 입력/출력 ( idx가 존재하지 않아 순열을 구한 코드 )

입력
4
2
1
2
12
1

출력
12
112
11
21
212
21
121
122
121
11
12
112

결과값
7