백준 5568: 카드 놓기[JAVA]

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

5568번: 카드 놓기

[난이도]

- Silver 4

 

[알고리즘]

- 부르트 포스

- 백트래킹

 

[코드]

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

public class Main {
    static int n, k;
    static boolean[] visited;
    static String[] arr;
    static ArrayList<String> list;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());
        k = Integer.parseInt(br.readLine());

        visited = new boolean[n];
        list = new ArrayList<>();

        arr = new String[n];
        for (int i = 0; i < n; i++) {
            arr[i] = br.readLine();
        }

        dfs(0, "");
        System.out.println(list.size());
    }

    static void dfs(int count, String tmp) {

        if (count == k) { // k개만 뽑는다
            if (!list.contains(tmp)) { // 이미 있는 숫자라면 추가하지 않음
                list.add(tmp);
            }
            return;
        }

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                visited[i] = true;
                dfs(count + 1, tmp+arr[i]);
                visited[i] = false;
            }
        }
    }
}

 

[풀이]

1. dfs 메서드는 한번 탐색할 때 마다 count 를 1 증가시키고, 인덱스의 값을 담는다.

2. count가 k가 될때 까지 반복한다. k가 될 경우 tmp에 담겨있는 값을 list에 추가한다. list에 이미 동일한 값이 있다면 추가하지 않는다.

3. 1, 2를 반복해 완점탐색을 한다.

4. list의 size를 출력한다.