Algorithm - ALLERGY

문제

집들이에 n명의 친구를 초대하려고 합니다. 할 줄 아는 m가지의 음식 중 무엇을 대접해야 할까를 고민하는데, 친구들은 각각 알러지 때문에 못 먹는 음식들이 있어서 아무 음식이나 해서는 안됩니다.
만들 줄 아는 음식의 목록과 해당 음식을 못 먹는 친구들의 목록이 주어진다고 합시다. 각 친구가 먹을 수 있는 음식이 최소한 하나씩은 있게
하려면 최소 몇 가지의 음식을 해야 할까요? 친구들의 정보가 주어질 때 최소한 만들어야 하는 요리의 가지수를 꼐산하는 프로그램을 작성하세요.

시간 및 메모리 제한

프로그램은 5초 안에 실행되어야 하며, 64MB 이하의 메모리를 사용해야 합니다.

입력

입력의 첫 줄에는 테스트 케이스의 수 T(0<= T <= 50)가 주어집니다. 각 테스트 케이스의 첫 줄에는 친구의 수 n(1<=n<=20)과 할 줄 아는 음식의 수 m(1<=m<=20)이 주어집니다.
다음 줄에는 n개의 문자열로 각 친구의 이름이 주어집니다. 친구의 이름은 50 이하의 알파벳 소문자로만 구성된 문자열입니다. 그 후 m줄에 하나씩 각 음식에 대한 정보가 주어집니다.
각 음식에 대한 정보는 해당 음식을 먹을 수 있는 친구의 수와 각 친구의 이름으로 주어집니다. 모든 친구는 하나 이상의 음식을 먹을 수 있다고 가정해도 좋습니다.

출력

각 테스트 케이스마다 한 줄에 만들어야 할 최소의 음식 수를 출력합니다.

풀이

문제 접근

먼저 완전 탐색으로 문제를 해결할 수 있는지 생각해본다. 여기서 완전 탐색이란 가능한 모든 음식의 조합을 모두 만들어보고 그 중 최솟값을 찾는 것을 의미한다. 음식의 가짓수가 최대 20개 이므로 탐색해야 하는 경우의 수는 2^20개가 된다.
2^20은 약 10^6이므로 시간안에 동작할 수 있을 것 같지만 최적화할 여지가 많으므로 가능한 최적화 방법을 생각해본다.

• 가능한 최적화 기법

  1. 적절한 휴리스틱을 이용한 가지치기
  2. 탐욕적 알고리즘으로 적절한 초기해 만들기
  3. 메모이제이션

탐욕적 알고리즘의 경우 이 문제에선 탐욕적 선택 속성이 적용되지 않기 때문에 믿음직스럽지 못하다. 메모이제이션의 경우 알고리즘을 이전까지 만들어온 상태와 무관하도록 파라미터를 조정한다면
중복을 발생시켜 최적화할 여지가 충분해 보인다. 하지만 지금은 조합 탐색을 공부하고 있기 때문에 가지치기를 우선적으로 시도해 보았다.

data type

본격적으로 문제를 풀기에 앞서, 어떤 자료형을 사용하는게 가장 적절할까 생각해 보았다. 친구들이 각 음식을 먹을 수 있는지의 여부를 1 혹은 0으로 표현할 수 있고, 현재 상태가
우리가 찾은 해인지의 여부를 시프트 연산자 및 bit-wise 연산자로 쉽게 구현할 수 있을 것이라고 생각했기 때문에 각 음식에 대한 정보를 담고 있는 데이터의 타입을 int의 배열로 설정했다. 하지만 중간에
특정 원소의 인덱스를 찾을 필요가 있었는데, Array에서는 이 기능을 지원하지 않기 때문에 자료형을 int의 배열에서 Integer의 ArrayList로 변경하였다.

Optimistic Heuristic

낙관적인 휴리스틱으로, 요리하는 음식의 수가 사람의 수를 넘는 경우를 생각해 보았다. 문제에는 모든 친구가 적어도 하나의 음식을 좋아한다고 가정하고 있으므로, 사람의 수보다 적은 음식 수의 조합에서 최적해가 무조건 있을 것이라고 예상할 수 있다.
그리고 추가적으로 생각할 수 있는 휴리스틱으로, 현재 만들고 있는 해가 지금까지의 최적해보다 클 경우에도 더 이상 탐색을 하지 않도록 하였다.

static void search(int currState, int currSolution, int currIdx) {
        //optimistic heuristic
        if(currSolution > min || currSolution > numOfPeople) return;


        //해를 찾지 못하고 배열의 끝까지 도달했을 때는 그냥 리턴(사실 도달할 수 없는 로직)
        if(currIdx == info.length) return;

        if(currState == ((1 << numOfPeople) -1)) {
            min = Math.min(currSolution, min);
            return;
        }

        //currIdx 번째 원소를 포함하는 경우
        search(currState | info[currIdx], currSolution + 1, currIdx + 1);

        //currIdx 번째 원소를 포함하지 않는 경우
        search(currState, currSolution, currIdx + 1);

    }

실행 결과는 아래와 같다.

2
10 7
a b c d e f g h i j
6 a c d h i j
3 a d i
7 a c f g h i j
3 b d g
5 b c f h i
4 b e g j
5 b c g h i
3
4 6
cl bom dara minzy
2 dara minzy
2 cl minzy
2 cl dara
1 cl
2 bom dara
2 bom minzy
2

책에서는 간단한 최적화 기법으로 탐색의 형태를 바꾸는 방법을 소개한다. 각 음식을 만들 것인가 여부를 선택하는 대신에, 매 재귀 호출마다 아직 먹을 음식이 없는 친구를 하나 찾은 뒤 이 친구를 위해 어떤 음식을 만들지를 결정하는 것이다.
앞선 탐색 방법의 경우 마지막 조각까지 결정한 뒤에도 음식을 먹지 못하는 친구가 남는 경우까지 모두 탐색하는 반면,
이 탐색 방법은 항상 모든 친구가 먹을 음식이 있는 조합만을 찾아낸다. 또한 원래의 알고리즘은 탐색의 깊이가 무조건 m으로 일정하지만, 이 탐색 방법은 호출 될 때마다 음식을 하나씩 하기 때문에 탐색의 깊이가 m보다 작아질 수 있다.

유념할 점

조합 탐색은 다른 접근방법처럼 문제해결 방법이 정해져 있는게 아니라, 상황에 따라 유동적으로 탐색의 가짓수를 줄일 수 있는 방법을 찾아야 한다. 그만큼 유연한 생각이 많이 필요하고 문제를 많이 풀어보아야 할 것 같다.