자바 알고리즘 문제 풀이 입문. ch08. DFS, BFS 활용 : 합이 같은 부분 집합 (DFS, 아마존 인터뷰)

 

https://hyejin.tistory.com/1265

자바 알고리즘 문제 풀이 입문. ch07. Recursive, Tree, Graph(DFS, BFS 기초) : 그래프 최단거리 (BFS)

-> 이전 문제 풀이 

 

 

 

1. 합이 같은 부분집합 (DFS, 아마존 인터뷰) 

설명

N개의 원소로 구성된 자연수 집합이 주어지면,

이 집합을 두 개의 부분집합으로 나누었을 때 두 부분집합의 원소의 합이 서로 같은 경우가 존재하면 “YES"를 출력하고, 그렇지 않으면 ”NO"를 출력하는 프로그램을 작성하세요.

둘로 나뉘는 두 부분집합은 서로소 집합이며, 두 부분집합을 합하면 입력으로 주어진 원래의 집합이 되어 합니다.

예를 들어 {1, 3, 5, 6, 7, 10}이 입력되면 {1, 3, 5, 7} = {6, 10} 으로 두 부분집합의 합이 16으로 같은 경우가 존재하는 것을 알 수 있다.

 

 

입력 설명

첫 번째 줄에 자연수 N(1<=N<=10)이 주어집니다.

두 번째 줄에 집합의 원소 N개가 주어진다. 각 원소는 중복되지 않는다.

 

 

출력 설명

첫 번째 줄에 “YES" 또는 ”NO"를 출력한다.

 

입력 예시 1

6
1 3 5 6 7 10

 

 

출력 예시 1 

YES

 

 

 

문제 풀이 1 

public class SubsetsWithTheSameSum2
{
   static String answer = "NO";
   static int n, total = 0;
   boolean flag = false;
   
   public void DFS(int L, int sum, int[] arr)
   {
      if (flag) return;
      if (sum > total/2) return;
      if (L == n) {
         if ((total- sum) == sum){
            flag = true;
            answer = "YES";
         }
      }else {
         DFS(L + 1, sum + arr[L], arr);
         DFS(L + 1, sum, arr);
      }
   }
   public static void main(String[] args)
   {
      SubsetsWithTheSameSum2 subsetsWithTheSameSum2 = new SubsetsWithTheSameSum2();
      Scanner scanner = new Scanner(System.in);
      n = scanner.nextInt();
      int[] arr = new int[n];
      
      for (int i = 0; i <n; i++)
      {
         arr[i] = scanner.nextInt();
         total += arr[i];
      }
      
      
      subsetsWithTheSameSum2.DFS(0, 0, arr);
      System.out.println("answer = " + answer);
      
   }
}

👾 :  

https://hyejin.tistory.com/1258

자바 알고리즘 문제 풀이 입문. ch07. Recursive, Tree, Graph(DFS, BFS 기초) : 부분집합 구하기 (DFS)

이전에 풀었던 부분집합 처럼 문제를 풀면 된다고 한다. 

문제에서 원하는 것이 주어진 집합에서 두 개의 부분 집합으로 나누었을 때 두 부분 집합의 원소의 합이 서로 같은 경우가 존재하면 yes를 리턴하라고 했다. 

 

 

 

 

-> 그림에서 처럼 D(0,0) 으로 시작해서, 다음 레벨로 넘어가서 원소 1을 포함한다, 포함하지 않는다 해서 

D(1,1) -> 레벨 1로 넘어가서 원소 1을 포함해서 총합이 0 +1 이라는 뜻이다.

D(1,0) -> 레벨 1로 넘어왔는데 원소 1을 포함하지 않고, 총합이 0 이라는 뜻이다. 

 

D(2,4) -> 레벨 2로 넘어와서 원소 3을 포함하고, 총합이 0 + 1 + 3 이라는 뜻이다.

D(2,1) -> 레벨 2로 넘어와서 원소 3을 포함하지 않고, 총합이 0 + 1 이라는 뜻이다. 

 

... 이렇게 반복해서 두 부분 집합의 합이 같은 경우가 있다면 YES 를 출력하면 된다. 

 

static String answer = "NO";
static int n, total = 0;
boolean flag = false;

이 문제에서는 우선 n, total, answer를 static 변수로 선언해준다. 그리고 flag에서는 두 부분 집합의 합이 같을 경우 true로 바꾸고, flag가 true이면 DFS를 종료하도록 한다. 

 

public void DFS(int L, int sum, int[] arr)
{
   if (flag) return;
   if (sum > total/2) return;
   if (L == n) {
      if ((total- sum) == sum){
         flag = true;
         answer = "YES";
      }
   }else {
      DFS(L + 1, sum + arr[L], arr);
      DFS(L + 1, sum, arr);
   }
}

-> L : 레벨을 뜻하고, sum 은 원소의 총 합, arr은 주어진 배열이다. (여기선 왜 갑자기 배열을 DFS에 포함시켰는지는.. 모르겠다 ㅋ) 

DFS이므로 if-else로 시작해준다. 먼저 L이 n이면 원소를 다 돌았다는 뜻이므로 여기서 이제 검증을 하는데 이때 
총합 total - sum이 sum 과 같다면 YES 로 answer 를 바꿔주고, flag를 true로 설정해준다. 

 

L이 n이 아니라면 DFS 재귀함수 호출을 통해 DFS(L+ 1, sum + arr[L] , arr) 과 DFS(L + 1, sum, arr) 를 호출해주는데 

앞에 DFS 호출은 해당 원소를 포함하여 더한 값을 넘겨주고, 뒤 DFS 호출은 해당 원소를 포함하지 않고 더한 값을 넘겨준다. 

 

if (flag) return;
if (sum > total/2) return;

DFS 호출 후 flag가 true이면 이미 값을 구했다는 뜻이므로 다른 값을 구해볼 필요가 없기 때문에 그대로 return 해주고, 

만약 sum이 total/2 값을 넘겨버렸다면 구하고자 하는 값이 아니므로 그냥 return 해준다.