Java - 17 DFS [java로 구현]

DFS의 개념은 아래 글을 참고한다.

doodreamcode.tistory.com/34?category=798601

자료구조 - 탐색알고리즘 DFS

DFS는 모든 경우의 수를 탐색할때 사용한다.

조합, 순열등 다양한 곳에서 사용가능하다.

 

DFS는 내부함수로서 구현이 된것이 아니기 때문에

필요할 때 마다 DFS라는 개념을 구현을 해야한다.

 

여기서는 java로 DFS를 짤 때의 틀을 정리하고자한다.

 

class Solution {
    private HashSet<HashSet<Integer>> resultSet;
    private String[] bannedId;
    private String[] userId;
    private boolean[] checked;

    public int solution(String[] user_id, String[]banned_id) {
        bannedId = banned_id;
        userId = user_id;
        resultSet = new HashSet<>();
        checked = new boolean[user_id.length];

        for (int i = 0; i < bannedId.length; i++) {
            bannedId[i] = banned_id[i].replace("*", ".");
        }
        dfs(0, new HashSet<>());

        return resultSet.size();
    }

    public void dfs (int index, HashSet<Integer> set){
        if(index == bannedId.length){
            resultSet.add(set);
            return;
        }

        for (int i = 0; i < userId.length; i++) {
            if(Pattern.matches(userId[i], bannedId[index]) && !checked[i])
                checked[i] = true;
                set.add(i);
                dfs(index + 1, new HashSet<>());
                checked[i] = false;
                set.remove(i);
        }

    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        String[] user_id = {"frodo", "fradi", "crodo", "abc123", "frodoc"};
        String[] banned_id = {"fr*d*", "*rodo", "******", "******"};
        System.out.println(solution.solution(user_id, banned_id));
    }
}

위 코드를 보면 DFS는

 

index : 재귀함수의 깊이

checked[i] : 방문을 했는지 안했는지 체크할 배열

 

이 필수적으로 필요하다.

    public void DFS(int index, 필요 인수들){

        if(index == 최대 깊이){
            return;
        }

        if(특정 조건을 만족하면 방문 && !checked[i]){
            checked[i] = true;
            dfs(index + 1, 필요인수들);
            // 방문을 하다가 특정조건이 계속 불만족한 경우
            // 방문을 취소
            checked[i] = false;
        }
    }

이러한 형식으로 DFS가 작성이되는 것을 알수 있다. 이러한 경우를 바탕으로 모든 경우의 수를

만드는 combination + permutation dfs를 개발하자.

 

 

package Programmers.Combination;


import java.util.ArrayList;
class Combination<T> {
    // 배열을 받아라
    private T[] user_id;
    private ArrayList<ArrayList<T>> resultArr;
    private boolean[] checked;

    public ArrayList<ArrayList<T>> solution(String[] user_id) {
        resultArr = new ArrayList<>();
        checked = new boolean[user_id.length];

        // 뽑을 갯수를 넣어라
        dfs(2, new ArrayList<>());
        return resultArr;
    }

    public void dfs(int selectAmount, ArrayList<T> arr) {
        if (arr.size() == selectAmount) {
            resultArr.add(arr);
            return;
        } else {
            for (int i = 0; i < user_id.length; i++) {
                if(!checked[i]){
                    // 리스트 사이즈가 뽑는 수보다 작아야지 dfs로 더 탐색한다.
                    checked[i] = true;
                    arr.add(user_id[i]);
                    // 기존에 있던 arr를 넣어야한다.
                    dfs(selectAmount, new ArrayList<>(arr));
                    checked[i] = false;
                    arr.remove(user_id[i]);
                }
            }
        }

    }

//    public static void main(String[] args) {
//        Solution solution = new Solution();
//        ArrayList<ArrayList<String>> answer = solution.solution(solution.user_id);
//        for (int i = 0; i < answer.size(); i++) {
//            for (int j = 0; j < answer.get(i).size(); j++) {
//                System.out.print(answer.get(i).get(j) + " ");
//            }
//            System.out.println("");
//        }
//        System.out.println(answer.size());
//    }

}

- 위코드는 제네릭으로 받아서 T 객체의 모든 순열을 받을수 있는것이다.