[백준]#13908 비밀번호

문제

웅찬이는 근성이 대단한 도둑이다. 그래서 금고를 털 때, 모든 조합을 눌러본다. 예를 들어 비밀번호가 3글자 라는 사실을 알 때, 000, 001, 002, 003, … 998, 999의 모든 조합을 눌러본다. 그러나 웅찬이는 선견지명이 있어서 비밀번호에 어떤 숫자가 들어가는지 일부 알 수 있다. 예를 들어 3글자 비밀번호에 0이 들어감을 안다면 999 와 같이 0이 들어가지 않는 수는 가능성이 없다. 그러나 000, 012, 030과 같은 수는 가능하다. 비밀번호의 길이와 선견지명으로 알게된 비밀번호의 일부 숫자가 주어질 때, 모든 가능한 비밀번호의 개수를 출력하는 프로그램을 작성하시오.

입력

첫줄에 비밀번호의 길이 n (1 ≤ n ≤ 7), 선견지명으로 알게된 비밀번호에 들어가는 수 m(0 ≤ m ≤ n) 이 주어지고, 둘째 줄에 m개의 서로 다른 숫자(0~9)가 주어진다.

출력

가능한 모든 비밀번호의 개수를 출력한다.

예제 입력 1

2 1
7

예제 출력 1

19

예제 입력 2

2 2
3 4

예제 출력 2

2

풀이

이 문제는 dfs(깊이 우선 탐색) 알고리즘을 이용해서 풀 수 있었다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;

public class Main {
    static int cnt = 0;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int n = Integer.parseInt(input[0]);
        int m = Integer.parseInt(input[1]);
        HashSet<Integer> set = new HashSet<>();

        input = br.readLine().split(" ");
        for(int i=0; i<m; i++) {
            set.add(Integer.parseInt(input[i]));
        }

        dfs(n, 0, set);

        System.out.println(cnt);
    }

    public static void dfs(int n, int idx, HashSet<Integer> set) {
        if(n-idx<set.size()) return;

        if(idx==n) {
            if(set.size()==0)
                cnt++;

            return;
        }

        for(int i=0; i<=9; i++) {
            if(set.contains(i)) {
                set.remove(i);
                dfs(n, idx+1, set);
                set.add(i);
            }

            else
                dfs(n, idx+1, set);
        }
    }
}