[APSS][알고스팟] 알러지가 심한 친구들 (ALLERGY)

[APSS][알고스팟] 알러지가 심한 친구들 (ALLERGY)

문제 정보

• 문제 ID : ALLERGY
• 시간 제한 : 5000ms
• 메모리 제한 : 65536kb

  문제

집들이에 n 명의 친구를 초대하려고 합니다. 할 줄 아는 m 가지의 음식 중 무엇을 대접해야 할까를 고민하는데, 친구들은 각각 알러지 때문에 못 먹는 음식들이 있어서 아무 음식이나 해서는 안 됩니다. 만들 줄 아는 음식의 목록과, 해당 음식을 못 먹는 친구들의 목록이 다음과 같은 형태로 주어진다고 합시다.

친구	갈비찜	피자	잡채	떡볶이	탕수육	닭강정
채린	x	o	o	o	x	x
봄	x	x	x	x	o	o
다라	o	x	o	x	o	x
민지	o	o	x	x	x	o

각 친구가 먹을 수 있는 음식이 최소한 하나씩은 있도록 하려면 최소 몇 가지의 음식을 해야 할까요? 위 경우라면 다 같이 먹을 수 있는 음식이 없기 때문에 결국 두 가지 이상 음식을 해야 합니다. 피자와 탕수육, 혹은 잡채와 닭강정처럼 두 개 이상의 음식을 선택해야만 모두가 음식을 먹을 수 있지요. 친구들의 정보가 주어질 때 최소한 만들어야 하는 요리의 가지수를 계산하는 프로그램을 작성하세요.

입력

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

출력

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

예제 입력

2
4 6
cl bom dara minzy
2 dara minzy
2 cl minzy
2 cl dara
1 cl
2 bom dara
2 bom minzy
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 

예제 출력

2
3

Solution

package apss;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.StringTokenizer;

public class Allergy {

        public static int N,M;
        public static Map<String, Integer> friends;
        public static int eatableCnt[];
        public static List<Integer> eatable[];
        public static List<Integer> canEat[];
        public static int eaten[];
        public static int result;

        public static void main(String[] args) throws NumberFormatException, IOException {
                // TODO Auto-generated method stub

                System.setIn(new FileInputStream("/Users/projooni/sample_input.txt"));
                BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

                int T = Integer.parseInt(br.readLine());
                for(int tc=1; tc<=T; tc++) {
                        StringTokenizer st = new StringTokenizer(br.readLine());
                        N = Integer.parseInt(st.nextToken());
                        M = Integer.parseInt(st.nextToken());

                        eaten = new int[N];
                        friends = new HashMap<String, Integer>();
                        result = Integer.MAX_VALUE;
                        eatable = new ArrayList[M];
                        canEat = new ArrayList[N];

                        st = new StringTokenizer(br.readLine());
                        for(int i=0; i<N; i++) {
                                friends.put(st.nextToken(), i);
                                canEat[i] = new ArrayList();
                        }

                        eatableCnt = new int[M];

                        for(int i=0; i<M; i++) {
                                st = new StringTokenizer(br.readLine());
                                eatableCnt[i] = Integer.parseInt(st.nextToken());
                                eatable[i] = new ArrayList();
                                for(int j=0; j<eatableCnt[i]; j++) {
                                        int friendNumber = friends.get(st.nextToken());
                                        eatable[i].add(friendNumber);
                                        canEat[friendNumber].add(i);
                                }
                        }

                        search(0,0);

                        bw.flush();
                        bw.write(result + "\n");

                }
                bw.close();

        }

        public static void search(int foodCount, int idx) {

                if(foodCount >= result) {
                        return;
                }

                int first  = 0;
                while(first < N && eaten[first] > 0) {
                        ++first;
                }

                // 모든 친구가 먹을 음식이 있는 경우 종료
                if(first == N) {
                        result = Math.min(result,foodCount);
                        return;
                }

                for(int i=0; i<canEat[first].size(); i++) {

                        int food = canEat[first].get(i);

                        List<Integer> eatableList = eatable[food];

                        for(int j=0; j<eatableList.size(); j++) {
                                eaten[eatableList.get(j)]++;
                        }

                        search(foodCount+1, idx+1);

                        for(int j=0; j<eatableList.size(); j++) {
                                eaten[eatableList.get(j)]--;
                        }

                }

        }

}

풀이

나름 혼자서 잘 접근했다. 다만 결정적으로 답으로 가기 위한 최적화까지 구현하지 못했다.
최적화의 핵심은 각 음식을 만들 것인가 여부를 선택하는 것 대신, 매 재귀 호출마다 아직 먹을 음식이 없는 친구를 하나 찾은 뒤 이 친구를 위해 어떤 음식을 만들지 결정하는 것이다.
이와 같은 탐색이 빠른 이유는 몇가지가 있다.

• search()(최적화 적용 알고리즘)은 항상 모든 친구가 먹을 음식이 있는 조합만을 찾아낸다. 반면 slowSearch()(최적화 미적용 알고리즘)는 마지막 조각까지 결정한 뒤에도 배고픈 친구가 남는 경우들도 모두 탐색하게 된다.
• search()는 한 번 호출될 때마다 항상 음식을 하나 하게 된다. 반면 slowSearch()는 음식을 하지 않고도 재귀 호출을 할 수 있다. slowSearch()의 깊이는 항상 m으로 고정되는 반면, search() 탐색의 깊이는 답과 같은데 답은 항상 m 이하의 숫자입니다.
• slowSearch()에서는 반드시 필요하지 않은 음식도 만드는 경우의 수가 있다. 이 음식을 먹을 수 있는 친구들은 이미 다 먹을 음식이 있는 경우다. 반면 search()에서는 음식을 한다는 말은 그 음식이 필요한 친구가 반드시 있다는 의미이다.