[DFS] 6. 부분 집합 구하기

<<풀이>>

 

항상 기억하자 DFS 문제는 if와 else 그리고 재귀함수로 되어 있다. 그리고 스택 프래임을 따른다!!

 

이 문제는 DFS를 사용하는데, 구성이 트리로 본다면 왼쪽은 추가 해준다. 오른 쪽은 추가 안 한다라고 잡고 시작을 한다.

이러한 원리로 해서 코딩 로직을 만들어 사용한다.

 

이때 ch이라는 배열의 초기화 시키고 왼쪽으로 가면 1를 추가해주고 오른쪽으로 가면 0을 추가해준다. 

그리고 난 뒤 재귀함수로 다음으로 넘어간다. 그러다가 총 원소 갯수가 일치하게 되면 ch 배열에 있는 1을 가지고 있는 인덱스를 반환하는 방식으로 문제를 푼다.

 

 

class Main{

    static int n;
    static int[] ch;
    public void DFS(int L) {
        if (L == n + 1) {
            String tmp = "";
            for (int i = 1; i <= n; i++) {
                if(ch[i] == 1) tmp += (i + " ");
            }
            if (tmp.length() > 0) System.out.println(tmp);

        }else {
            ch[L] = 1;
            DFS(L + 1);
            ch[L] = 0;
            DFS(L + 1);
        }
    }

    public static void main(String[] args) {
        Main T = new Main();
        n = 3;
        ch = new int[n + 1];
        T.DFS(1);
    }
}

 

재귀함수에 대해 전체적인 이해도를 올리고 있지만 아직 부족한 것 같다. 계속 꾸준히 공부해 나가자.