DFS 기초 - 부분집합

---

{1,2,3} 라는 배열이 있을때

먼저 1을 사용 한다 / 안한다로 나눌수 있다

1을 사용 한다 -> 2를 사용 한다/안한다

1을사용 안한다 -> 2를 사용 한다/안한다 이렇게 트리로 나아갈 수 있다.

 

전체소스

package test;

public class test {
	
	static int[] dice = { 1,2,3,4,5 };
	static int[] ch = new int[6];

	
	public static void dfs(int LV) {
		
		if(LV==5) {
			for(int i=0; i<6; i++) {
				if(ch[i]==1) {
					System.out.print(i+" ");
				}
			}System.out.println();
		}else {
			ch[LV]=1;
			dfs(LV+1);
			ch[LV]=0;
			dfs(LV+1);
		}

	}

    public static void main(String[] args) {
 
    	dfs(1);
    }
}

결과값

 

이 중에서 3개의 조합이 됐을때만 뽑는다면 카운트를 넣어줄 수 있다.

package test;

public class test {
	
	static int[] dice = { 1,2,3,4,5 };
	static int[] ch = new int[6];
	static int cnt=0;

	
	public static void dfs(int LV) {
		
		if(LV==5&&cnt==3) {
			for(int i=0; i<6; i++) {
				if(ch[i]==1) {
					System.out.print(i+" ");
				}
			}System.out.println();
		}else if(LV<6) {
			ch[LV]=1;
			cnt++;
			dfs(LV+1);
			ch[LV]=0;
			cnt--;
			dfs(LV+1);
		}

	}

    public static void main(String[] args) {
 
    	dfs(1);
    }
}