DFS 조합, 모든 경우의 수

문제

N, R, P 각각의 인풋이 주어진다.

N은 필름의 개수이고 R과 P는 필름의 특성값이다.

R은 곱의 성능, P는 합의 성능이라고 할때 R과 P의 차이값이 최소인 경우가 가장 필름화면의 성능이 우수한 경우이다.

주어진 N개의 필름에서 최적의 성능을 위해 제거할 필름의 최대갯수를 구하라

 

입력

4

2 10

2 8

3 4

4 12

 

출력

1

---

문제해결

모든 경우의 수를 조합하는 것이다. 모든 경우의 수는 조합이며 조합은 즉, DFS로 접근 가능하다. DFS를 조합으로 나타낼때 다중트리나 이중트리로 접근한다. 다중트리는 노드를 중심으로, 이중트리는 노드의 방문 혹은 선택여부를 중심으로 판단한다.

 

※ 재귀함수 추적시 확인점

0. 함수 Call되어 Stack caller에 쌓인 경로

1. Code에 의해 Return한 시점

2. Return 후 다음 code 문장 수행 시점

3. 함수 완전 수행에 의해 함수 종료한 시점

 

DFS는 주로 아래의 구조를 가진다.

1. 파라미터 설정 : DFS에서 조합과 순열에 따라 시작노드, level, 문제해결에 필요한 인자들을 설정한다.
※ 조합은 level과 시작 노드가 필요하고, 순열은 level만 필요하다.

2. 종료조건 : DFS는 재귀함수이기 때문에 반드시 종료 조건이 필요하다. 그렇지 않으면 무한 재귀에 빠질 수 있다. 종료 조건을 설정할 시에는 반드시 확산하는 트리를 구상하고 설정해야한다.
예를 들어, level에 따라 종료할지, 시작노드에 따라 종료할지 잘 따져보아야한다.

3. 해당노드에서 할일 : 해당 노드에서 수행할 작업이다. 이 문제에서는 합과 곱의 차이를 최소값으로 갱신하는 작업일 것이다. 종료조건에 따라 확산 후에도 해당 노드에서 할일을 수행하지 못할 수도 있다. 때문에 종료조건과 함께 할일을 먼저 선행할 것인지, 잘 따져보아야한다.

4. 확산 : 확산시에는 visit방문 처리를 해야하는지, 특정 경우에만 확산하도록 할 것인지 잘 확인해야한다.

5. 확산 후 : 확산 후 return하여 해당 노드로 돌아왔을때 수행할 일이다. 주로 visit방문처리를 초기화하는 등의 backtracking 작업이 있다. backtracking을 필요로 하지 않을 경우 아무것도 하지 않아도 된다.

 

이 문제는 조합이다. 노드를 선택하는 순서가 중요하지 않다. 또한, 노드마다 파라미터로 곱셈과 덧셈의 값을 전달해주어야 한다. DFS의 확산에서는 2가지 방법이 있는데, 다중트리로 구성하는 방법과 이진트리로 구성하는 방법이 있다.

트리를 한번 구성해보자.

위 그림처럼 트리가 진행됨에 따라 전달되는 파라미터의 값들을 생각하면 이해에 도움이 될 것이다. 주의할 것이 종료조건 과 노드에서 처리해야할 일의 순서와 조건들이다. 예를 들어 단순하게 생각하여 Input이 4개이니 idx가 4보다 크게 되면 return하면 되겠다고 생각하자. 그리고 종료조건을 먼저 수행하였다.

void Dfs(int idx, int level, ...)
{
	//종료조건
    if(idx>4)
    {
    	return;
    }
    
    //node에서 수행할 일
    ;
    
    //확산
    for(int i=0; i<4; i++)
    {
    	;
	}
}

위의 코드대로 되었다고 하면 그림에서와 같이 1-2-3을 통해 확산된 4의 노드에서 노드를 방문하자 마자 return하게 된다. 즉, 노드 방문처리가 제대로 수행되지 않고 종료되는 것이다. 그러면 모든 경우의 수를 확인할 수 없게 되는 것이다. 

따라서 올바른 종료조건이 설정 되었는지 반드시 확인해야한다. 노드에 방문하자마자 할일을 수행하고 종료조건을 걸던, 종료조건을 바꾸던 수정해야하는 것이다. 다중트리로 구현한 코드를 보자.

#include <stdio.h>

#define MAX ((int)1e6)

int N;
int R[10+2]; //곱
int P[10+2]; //차
//가장 작은 조합찾기
long long mindiff;
int mincnt;
int ans = MAX;

void Input()
{
	scanf("%d", &N);
	
	for(int i=1; i<=N; i++){
		scanf("%d",&R[i]);
		scanf("%d",&P[i]);
	}
	
}

void Myprint()
{
	printf("%d\n",N);
	for(int i=1; i<=N; i++){
		printf("%d %d\n",R[i],P[i]);
	}
}

long long ABS(long long mul, long long sum){
	return (mul-sum) > 0 ? mul-sum : sum-mul;
}

void MyDFS(int idx, int cnt, long long mul, long long sum){
	//printf("idx : %d, cnt : %d __ mul : %d, sum : %d\n", idx, cnt, mul, sum);
	
	if(cnt>0)
	{
		long long sub = ABS(mul,sum);
		if(ans>sub || (ans==sub && mincnt > cnt))
		{
			ans = sub;
			mincnt = cnt;
		}			
	}
	
	if(idx>N)
	{
		//printf("RETURN / idx : %d \n",idx);
		return;
	}
	
	//다중
	for(int i =idx; i<=N; i++)
	{
		MyDFS(i+1, cnt+1, mul*R[i], sum+P[i]);
	}
}



int main() {
	Input();
	MyDFS(1,0,1,0); //시작노드, 여태 선택한cnt, mul, sum
	
	printf("%d", N - mincnt);
	
	return 0;
}

 

---

다른 방법으로 이진트리를 한번 보자. 노드를 선택하고, 선택하지 않고 에 따라서 트리를 구성해 나가는 것이다. 아래 그림을 보자.

1번, 2번 부터 6번이 트리를 순회하는 순서일 것이다. 이때에도 다중트리와 종료 조건이 달라 질 수 있으니  반드시 확인해야한다. 예를 들어 cnt level로 종료조건을 구성했다고 했을때 이 이진트리에서는 문제가 되지 않을까? 이진트리에서는 선택할때마다 cnt값을 올릴 것이다. 트리의 맨 우측 처럼 노드가 진행되감에도 level이 하나도 증가하지 않는 case가 있을 수 있다. 이런 경우에 level을 단순하게 종료조건으로 설정하면 무한 재귀에 빠질 수 있다.

이진트리의 코드를 보자.

 

#include <stdio.h>
#define MAX (int)1e6
int N; 
int R[10+3]; 
int P[10+3]; 
long long mindiff = MAX;
int ans;
void Input()
{
	scanf("%d", &N)	;
	for(int i=1; i<=N; i++)
	{
		scanf("%d %d", &R[i], &P[i]);
	}
}

long long ABS(long long x)
{
	return x > 0 ? x : -x;
}

void Dfs(int idx, int cnt, long long mul, long long sum)
{	
	if(idx>N+1)
	{
		return;
	}
	
	if(cnt>0)
	{
		long long sub = ABS(mul-sum);
		if(mindiff>sub || ((mindiff==sub) && (ans>cnt) ))
		{
			mindiff = sub;
			ans = cnt;
		}
	}
	
	Dfs(idx+1, cnt, mul, sum);
	Dfs(idx+1, cnt+1, mul*R[idx], sum+P[idx]);
}


int main() {
	Input();
	
	Dfs(1,0,1,0); //시작idx, cnt, mul, sum
	
	printf("%d", N-ans);
	return 0;
}