문제: 알러지가 심한 친구들
이 문제는 문제 해결을 위한 자료 구조를 어떻게 표현해야 할지를 잘 고민 해야 한다. 당연히 여러가지 푸는 방법이 있겠지만, 본 포스팅에서는 특정 음식에 대해서 어떤 사람이 먹을 수 있는지 Binary 로 표시하였다. 예시된 케이스 중 다음의 케이스로 설명 하겠다.
4 6 cl bom dara minzy 2 dara minzy 2 cl minzy 2 cl dara 1 cl 2 bom dara 2 bom minzy |
이 케이스는 다음의 표로 표시가 가능하다.
|
0 |
1 |
2 |
3 |
4 |
5 |
cl |
0 |
1 |
1 |
1 |
0 |
0 |
bom |
0 |
0 |
0 |
0 |
1 |
1 |
dara |
1 |
0 |
1 |
0 |
1 |
0 |
minzy |
1 |
1 |
0 |
0 |
0 |
1 |
음식0번은 1100, 음식1번은 1001, 음식2번은 0101 로 long 형의 Binary로 해당 음식을 표현한다.
모든 사람이 먹게 하기 위해서는 상기 케이스의 경우 1111 을 만족하는 각 음식의 Binary 조합이 필요하다. 예를 들어 음식 1번 1001 과 음식 4번 0110 이 최적이 되는 이다. 물론 다른 해도 있을 수 있다.
이를 계산하기 위해서는 음식 하나를 선택하고 추가하면서 추가된 음식의 2진 값을 OR 연산을 하여 1111이 되는 최소 추가 횟수를 구하면 된다. 그리고 단순히 재귀 함수만 사용할 경우 호출에 대해서 최적화 되지 않는다. 두가지 점에서 재귀 함수를 최적화 해야 하는데,
1. 현재 어떤 음식을 추가하는 상황에서 이미 이전에 문제가 해결이 되었고, 지금 추가하는 갯수가 풀어진 해의 추가 갯수의 최소보다 크다면 더이상 실행할 필요가 없다. 따라서 다음의 최적화 코드를 재귀 함수에 넣는다.
if(mSolved && mMinFoods<depth) return; |
2. 재귀 함수로 넘겨지는, 남겨져 있는 음식의 셋에서 무시해도 되는 셋이 있다. 예를 들어 상기 케이스에서 0번 음식을 선택하고 (1100) 다음 음식 1번은 선택하면 현재까지 풀은 해는 1101 이 되는데 이 경우 다음 재귀 함수 호출시 음식 셋에서 음식 2, 3번을 제외해도 무관하다. 즉 음식 1,2,3은 음식 0번을 선택했을 경우 동일한 결과를 나타내는 것이다. 따라서 다음 재귀 함수로 호출하는 음식 셋에서 2,3번은 제외해야 한다. 따라서 재귀 함수에 다음의 코드를 넣는다.
Queue<Long> newSet=new LinkedList<Long>(); int setSize=set.size(); for(int i=0;i<setSize;i++){ long cmp=set.remove().longValue(); if((cmp|solved)!=newSolved){ newSet.add(cmp); set.add(cmp); } } //callCount++; solvIter(newSet,newSolved,depth+1); |
다음은 알고스팟에서 통과된 코드이다.
