[C/C++] DFS 60. 합이 같은 부분집합(DFS : 아마존 인터뷰)

문제

N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나누었을 때
두 부분집합의 원소의 합이 서로 같은 경우가 존재하면 “YES"를 출력하고, 그렇지 않으면
”NO"를 출력하는 프로그램을 작성하세요.
예를 들어 {1, 3, 5, 6, 7, 10}이 입력되면 {1, 3, 5, 7} = {6, 10} 으로 두 부분집합의 합이
16으로 같은 경우가 존재하는 것을 알 수 있다.

 

입력설명
첫 번째 줄에 자연수 N(1<=N<=10)이 주어집니다.
두 번째 줄에 집합의 원소 N개가 주어진다. 각 원소는 중복되지 않으며 그 크기는 1,000,000
이하입니다.

 

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

문제 풀이

DFS로 푸는 문제이다. 이 문제는 각 자연수를 선택할 지, 아닐지에 대한 문제로, DFS를 통해 각 함수가 포함되고 안 포함되고를 구현하면 된다.

 

주요 함수부터 살펴보자.

DFS는 항상 if-return을 통해 DFS가 종료되는 지점을 잡아줘야 한다. 잡아주지 않으면 무한루프에 빠지게 됨.

 

주요 부분은 아래와 같다.

void DFS(int x, int tmp)
{
	if (x>n)
	{
		return;
	}
	
	if (tmp==sum-tmp)
	{
		flag = true;
	}
	
	DFS(x+1, tmp+arr[x]);
	DFS(x+1, tmp);
}

우선 설명한 내용은 DFS 함수에서 아래,

DFS(x+1, tmp+arr[x]);

DFS(x+1, tmp); 부분이다.

 

첫 번째 DFS는 x (횟수)를 늘려가면서 arr[x];을 더하게 된다. 횟수에 해당하는 배열 값을 더하는 것이다.

가장 맨 처음에 DFS가 돌 때는 결과적으로 횟수를 늘려가면서 모든 배열 값을 더하게 된다.

따라서 집합의 모든 값을 더하게 된다.

 

[1, 2, 3]이라는 배열이 있었다고 하자. 그리고 DFS 함수가 처음 계속 돌면 DFS(x+1, tmp+arr[x]);만 만나게 된다.

그러면 모든 집합을 더하다가 x>n이 되어 if-return을 만나서 return된다. 1+2+3을 모두 더한 것이다.

그렇다면 return되었으니 x+1에서 하나 이전인 x값을 가지는 함수로 돌아가게 된다. 그리고 그 다음 DFS(x+1, tmp);를 만나게 된다. 이 함수는 횟수는 늘어나는 데, x 값에 맞는 배열은 더하지 않는다. 즉 선택하지 않는 것이다. 그리고는 x>n 조건에 따라 다시 return된다.

 

즉, 가장 맨 처음에는 1,2,3을 모두 더했고, 그 다음에는 1,2를 더하고 3은 선택하지 않아 더해지지 않은 것이다. 이를 반복한 그림은 아래와 같다. 횟수를 늘려나가면서 배열을 선택할 지, 안할지 모두 위에 두 DFS함수에 달려있다.

 

그림을 보며 이해할 수 있지만 실제로 그려보는 게 가장 이해가 쉽다.

DFS그림

 

그리고 문제에서 더한 값이 나머지 값과 같을 때이므로, 집합 전체를 더한 겂에 반만큼만 더해지면 완료된다.

이 때, if (tmp=sum-tmp) 조건을 사용한 것을 알 수 있다. if(tmp==sum/2)으로 쓰면 되지 않냐고? 절대 아니다. 

등호 조건을 볼 때는 나누기에 대해 굉장히 조심스러워야한다. 버림처리 되기 때문에 원하지 않는 값이 나올 수 있다. 오히려 위에처럼 적어주는 게 정답이다. 초반에 그래서 오답이 나오게 되었었다.

 

전체 풀이는 아래와 같다.

#include <iostream>
#include <vector>
#include <string>
#define MAX 15
using namespace std;

int n;
int arr[MAX];	
int sum;
bool flag=false;

void input()
{
	for (int i=1; i<=n; i++)
	{
		cin>>arr[i];
		
	}
	
	for (int i=1; i<=n; i++)
	{
		sum+=arr[i];
	}
}

void DFS(int x, int tmp)
{
	if (x>n)
	{
		return;
	}
	
	if (tmp==sum-tmp)
	{
		flag = true;
	}
	
	DFS(x+1, tmp+arr[x]);
	DFS(x+1, tmp);
}

int main()
{	
	cin>>n;
	input();
	DFS(1,0);
	
	if (flag==true)
	{
		cout<<"YES"<<endl;
	}
	else
	{
		cout<<"NO"<<endl;
	}
	
	return 0;	
}

Reference

it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비