[인프런 자바/java] 1. 합이 같은 부분집합(DFS : 아마존 인터뷰) _디버깅의 눈물

체크 포인트

 

1. DFS(깊이 우선 탐색)을 이용하는 문제

-두 부분집합의 합이 '같은 경우'가 존재하는 지 확인하는 문제

-해당 경우가 존재하는지 모두 탐색하기 위해 DFS 활용

 

 

2. 모집합의 총합이 홀수인 경우 체크

 

    	// 전체 원소의 합이 짝수인 경우에만 실행,
    	if(sumLimit%2 == 0){
    		// 전체 합의 절반이 되어야 두 부분집합의 합이 동일할 수 있다.
        	sumLimit = sumLimit/2; 
        	// DFS탐색 시작
        	DFS(0,0);
        	
    	}

 

-모집합의 총합이 홀수인 경우, 두 부분집합의 합은 동일할 수가 없다.

-부분집합은 2개만 존재하기 때문이다.

-따라서 해당 경우의 수를 DFS 탐색 전에 처리했다.

 

 

3. '하나의 부분집합 원소의 총합'이 '전체 원소의 합/2인 경우'를 탐색

 

 

4. 두 가지 경우의 수로 나누어서 DFS 탐색

 

    	// 현재 단계가 원소 배열의 마지막이 아니라면,
    	if(L != N){
    		// 해당 원소를 합한 경우,
    		DFS(L+1, sum+arr[L]);
    		// 해당 원소를 합하지 않은 경우,
    		DFS(L+1, sum);
    	}

 

-해당 원소를 

(1)부분집합의 합으로 계산할 것인지

(2)부분집합에 포함시키지 않을 것인지로 나누어 탐색

 

 

 

5. 정답이 존재하는 경우 더 이상 탐색할 필요가 없으므로, return 처리

 

    	// 정답인 경우가 존재한다면 탐색 중단
    	if(answer.equals("YES")){
    		return;
    	}

 

 

 

풀이

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public  class Main {
	// 집합 원소의 개수 N
	static int N;
	// 집합의 원소가 들어가는 배열
	static int[] arr;
	// 부분 집합 원소의 총합
	static int sum;
	// 전체 집합 원소의 총합/2
	static int sumLimit;
	// 정답
	static String answer;
	
    public static void main(String[] args) throws IOException {
    	
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	// 전체 집합 원소의 개수
    	N = Integer.parseInt(st.nextToken());
    	// 배열 초기화
    	arr = new int[N];

		st = new StringTokenizer(br.readLine(), " ");
		// 배열 값 입력
    	for(int i=0; i<N; i++){
    		arr[i] = Integer.parseInt(st.nextToken());
    		sumLimit += arr[i];
    	}
    	
    	/*
    	for(int i=0; i<N; i++){
    		System.out.print(arr[i] + " ");
    	}
    	*/
    	
    	// 정답 초기화
    	answer = "NO";
    	
    	// 전체 원소의 합이 짝수인 경우에만 실행,
    	if(sumLimit%2 == 0){
    		// 전체 합의 절반이 되어야 두 부분집합의 합이 동일할 수 있다.
        	sumLimit = sumLimit/2; 
        	// DFS탐색 시작
        	DFS(0,0);
        	
    	}
    	
    	System.out.println(answer);
    }
    
    static void DFS(int L, int sum) {
    	// 정답인 경우가 존재한다면 탐색 중단
    	if(answer.equals("YES")){
    		return;
    	}
    	// 현재까지 원소의 합이 제한을 넘는다면,
    	if(sum>sumLimit){
    		return;
    	}
    	
    	// 현재까지 원소의 합이 정답이라면,
    	if(sum==sumLimit){
    		// 정답 처리
    		answer = "YES";
    		return;
    	}
    	
    	// 현재 단계가 원소 배열의 마지막이 아니라면,
    	if(L != N){
    		// 해당 원소를 합한 경우,
    		DFS(L+1, sum+arr[L]);
    		// 해당 원소를 합하지 않은 경우,
    		DFS(L+1, sum);
    	}
    	
    }
    

} // end of Main