[자바] 백준 5568번 카드 놓기

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

 

마찬가지로 DFS를 활용한 완전탐색로 푸는 문제였다. 익숙해졌다고 생각했는데 조금만 응용해서 나오면 못 푸는 게 현타가 오지만..^^ 다시 풀어보다보면 감을 잡겠지..

 

이 문제는 visited를 확인해줬어야 했는데, dfs에 처음에는 0과 빈 문자열을 넣어주고, depth를 늘려서 결국 k의 값과 같은 경우에 대해서만 arrayList에 add 하면 된다. 하지만 이때 arrayList에 이미 있는 수에 대해서는 넣으면 안되기 때문에 contains로 이미 존재하는 값에 대해서 비교해준다. 문자열로 입력 받는 이유는 순서를 바꿔서 단순히 숫자를 문자열처럼 합치는 작업이기 때문에 숫자로 하면 서로 더해진다는 문제가 생긴다. 

그리고 for문을 카드의 개수만큼 돌면서 visited가 false면 들어가서 depth를 하나 늘리고, 현재의 문자열과 i에 해당하는 문자(arr[i]의 원소에 해당하는 카드)를 꺼내서 더한다. 그리고 dfs 함수에서 depth가 동일해서 return 됐다면 visited[i]를 다시 true로 만들어서 여러 번 다른 문자와 합쳤을 때의 값을 확인할 수 있도록 설정한다.

 

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

public class Main{
    public static boolean[] visited;
    public static int n, k, cnt;
    public static ArrayList<String> arrayList = new ArrayList<>();
    public static String[] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        k = Integer.parseInt(br.readLine());
        arr = new String[n];
        for(int i = 0; i < n; i++){
            arr[i] = br.readLine();
        }
        
        visited = new boolean[n];
        dfs(0, "");
        System.out.println(arrayList.size());
        
    }
    public static void dfs(int depth, String a){
        if(depth == k){
            if(!arrayList.contains(a)){
                arrayList.add(a);
            }
            return;
        }
        for(int i = 0; i < n; i++){
            if(!visited[i]){
                visited[i] = true;
                dfs(depth+1, a+arr[i]);
                visited[i] = false;
            }
        }
    }
}