[종만북] 알러지가 심한 친구들 음식 메뉴 정하기 - 완전탐색(BruteForce) + 재귀호출(Recursion) JAVA

출처 : 4.4 지수시간 알고리즘 - 알러지가 심한 친구들, 모든 답 후보를 평가하기

코드설명

집들이에 N명의 친구가 초대되고, 할 줄 아는 M가지 음식 중 무엇을 대접할지 설정해야 합니다.

이떄, 친구들은 각각 알러지 때문에 못 먹는 음식들이 있어서 아무 음식이나 해서는 안됩니다.

각 친구가 먹을 수 있는 음식이 최소한 하나씩 있으려면 최소 몇가지의 음식을 해야하는지 구하시오.

 

아래의 테스트케이스는 직접 만들어보았습니다.

테스트케이스

 

집들이에 초대된 친구들의 수(N), 준비할 수 있는 음식의 종류 수(M), 그리고 친구들마다 먹을 수 없는 음식의 리스트가 주어집니다.

• 1번 친구는 5번, 6번 음식을 못 먹습니다.
• 2번 친구는 1번, 2번, 3번, 4번 음식을 못 먹습니다.
• 3번 친구는 2번, 4번, 6번 음식을 못 먹습니다.
• 4번 친구는 3번, 4번, 5번 음식을 못 먹습니다.

4 6
1 5 6
1 2 3 4
2 4 6
3 4 5

 

결과 1

2

코드

1. void 타입으로 simulation 재귀함수를 만들었습니다.

시간복잡도는 O( (2^M )*N*M) 입니다.

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.StringTokenizer;

public class Main {
	public static int N, M;
	public static HashSet<Integer>[] friendAllergySet;
	public static int answer = 0;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		answer = M;
		
		friendAllergySet = new HashSet[N];
		for(int i=0;i<N;i++) {
			friendAllergySet[i] = new HashSet<Integer>();
		}
		
		//모두 먹기 위해서는, 알러지가 있는 것을 저장하는 것이 아닌 알러지가 없는 
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine());
			while(st.hasMoreElements()) {
				int foodIdx = Integer.parseInt(st.nextToken());
				friendAllergySet[i].add(foodIdx - 1);	
			}
		}
		
		simulate(0, new ArrayList<Integer>());
		System.out.println(answer);
	}
	
	public static void simulate(int level, ArrayList<Integer> menu) {
		if(level == M) {
			//만약 모두 먹을 수 있는 음식조합이라면, 최소 몇가지의 음식을 해야하는지.
			if(canEverybodyEat(menu) == true) {
				answer = Math.min(answer, menu.size());
			}
			return ;
		}
		
		//해당 level을 선택하는 경우
		menu.add(level);
		simulate(level + 1, menu);
		menu.remove(menu.size() - 1);
		
		//해당 level을 선택하지 않는 경우
		simulate(level + 1, menu);
	}
	
	public static boolean canEverybodyEat(ArrayList<Integer> menu) {
		for(int i=0;i<N;i++) {
			boolean isEatable = false;
			for(int menuNum : menu) {
				//만약 친구가 해당 음식을 아예 못먹는경우를 제외해야 합니다.
				if( !friendAllergySet[i].contains(menuNum)) {
					isEatable = true;
					break;
				}
			}
			//만약 아예 못먹는경우 return false;
			if(isEatable == false) {
				return false;
			}
		}			
		return true;
	}
	
}

 

2. int 반환형으로 진행할경우입니다.

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.StringTokenizer;

public class Main {
	public static int N, M;
	public static HashSet<Integer>[] friendAllergySet;
	public static int answer = 0;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		answer = M;
		
		friendAllergySet = new HashSet[N];
		for(int i=0;i<N;i++) {
			friendAllergySet[i] = new HashSet<Integer>();
		}
		
		//모두 먹기 위해서는, 알러지가 있는 것을 저장하는 것이 아닌 알러지가 없는 
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine());
			while(st.hasMoreElements()) {
				int foodIdx = Integer.parseInt(st.nextToken());
				friendAllergySet[i].add(foodIdx - 1);	
			}
		}
		
		answer = simulate2(0, new ArrayList<Integer>());
		System.out.println(answer);
	}
	
	public static int simulate2(int level, ArrayList<Integer> menu) {
		if(level == M) {
			//만약 모두 먹을 수 있는 음식조합이라면, 최소 몇가지의 음식을 해야하는지.
			if(canEverybodyEat(menu) == true) {
				return menu.size();
			} 
			return M;			
		}
		
		int res;
		//해당 level을 선택하는 경우
		menu.add(level);
		res = simulate2(level + 1, menu);
		menu.remove(menu.size() - 1);
		
		//해당 level을 선택하지 않는 경우
		res = Math.min(res, simulate2(level + 1, menu));		
		return res;
	}
	
	public static boolean canEverybodyEat(ArrayList<Integer> menu) {
		for(int i=0;i<N;i++) {
			boolean isEatable = false;
			for(int menuNum : menu) {
				//만약 친구가 해당 음식을 아예 못먹는경우를 제외해야 합니다.
				if( !friendAllergySet[i].contains(menuNum)) {
					isEatable = true;
					break;
				}
			}
			//만약 아예 못먹는경우 return false;
			if(isEatable == false) {
				return false;
			}
		}			
		return true;
	}
	
}

 

3. Hashset과 재귀함수 활용한 코드입니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.StringTokenizer;
 
public class Main {
	public static int C, N, M;
	public static int answer = Integer.MAX_VALUE;
	public static HashSet[] hashset;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		hashset = new HashSet[N];
		for(int i=0;i<N;i++) {
			hashset[i] = new HashSet<Integer>();
			st = new StringTokenizer(br.readLine());
			while(st.hasMoreElements()) {
				hashset[i].add(Integer.parseInt(st.nextToken()));
			}
		}
		System.out.println(selectMenu(new ArrayList<Integer>(), 1));
		
	}
	
	public static int selectMenu(ArrayList<Integer> foodList, int foodIdx) {
		//기저사례 1 : 최대 메뉴에 도달한다면,  
		if(foodIdx == M + 1) {
			for(int v : foodList) {
				System.out.print(" "+v);
			}
			System.out.println();
			if(canEveryBodyEat(foodList) == true) {
				return foodList.size();
			}
			return Integer.MAX_VALUE;
		}
		
		//해당 음식(foodIdx) 선택안하는 경우
		int ret = selectMenu(foodList, foodIdx + 1);
		
		//해당 음식(foodIdx) 선택하는 경우
		foodList.add(foodIdx);
		ret = Math.min(ret, selectMenu(foodList, foodIdx + 1));
		foodList.remove(foodList.size() - 1);
		return ret;
	}
	
	public static boolean canEveryBodyEat(ArrayList<Integer> foodList) {
		
		for(int i=0;i<N;i++) {
			boolean isEatable = false;
			for(int j=0; j<foodList.size(); j++) {
				if(hashset[i].contains(foodList.get(j)) == false) { //만약 해당 음식 중 모두 알러지가 있다면 실패.
					isEatable = true;
					break;
				}
			}
			if(isEatable == false)
				return false;
		}
		return true;
		
		
	}
	
	
}

 

3. 문제와 조금 다른 조건으로 코딩했습니다. 만약 M을 고정하지 않고, 1부터 최대 M개로 선언하여 진행했습니다.

 

ArrayList로 활용한 코드입니다. 먹을 수 있는 음식을 검색하는 과정에서 더 많은 리소스가 소요되기에 HashSet을 사용하는것이 훨씬 좋습니다. 하지만, 이런 객체 상태로 처리할경우에는 HashSet 사용이 어려우므로 ArrayList를 사용했습니다. 가끔 객체를 사용하면 생기는 제약사항을 삭제하기 위해서는 HashSet[] 배열 사용을 생각하는것이 문제 Solving에 더 효과적이라 생각됩니다.

또, 위의 코드와 다르게 for문을 활용하여 조합문을 완성했습니다. 음식을 선택하냐 선택하지 않느냐 두가지로 나눠서 하므로 위의 코드가 더 직관적입니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class Main {
	public static int C, N, M;
	public static int answer = Integer.MAX_VALUE;
	public static Friend[] friend;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		friend = new Friend[N];
		
		for(int i=0;i<N;i++) {
			ArrayList<Integer> notEatList = new ArrayList<Integer>();
			friend[i] = new Friend();
			st = new StringTokenizer(br.readLine());
			while(st.hasMoreElements()) {
				notEatList.add(Integer.parseInt(st.nextToken()));
			}
			friend[i].notEatList = notEatList;
		}
		
		System.out.println(findMinFoodKind(new ArrayList<Integer>(), 1));
	}

	public static int findMinFoodKind(ArrayList<Integer> foodList, int foodIdx) {
		int ret = Integer.MAX_VALUE;
		if(isEveryoneCanEatForOnce(foodList) == true) {
			ret = Math.min(ret, foodList.size());
		}
		
		for(int i=foodIdx; i<=M; i++) {
			foodList.add(i);
			ret = Math.min(ret, findMinFoodKind(foodList, i + 1));
			foodList.remove(foodList.size() - 1);
		}
		
		return ret; 
		
	}
	
	//각 친구가 먹을 수 있는 음식이 하나라도 있어야 합니다.
	public static boolean isEveryoneCanEatForOnce(ArrayList<Integer> foodList) {

		//친구 반복문
		for(int i=0;i<N;i++) {
			int allergeCnt = 0;
			//각 음식 중에 먹을 수 있는 음식이 하나라도 있어야 합니다. (즉, 알레르기가 없는 경우가 있어야합니다.)
			for(int j=0; j<foodList.size();j++) {

				for(int k=0; k<friend[i].notEatList.size();k++) {
					//알레르기 음식일 경우 개수를 모두 셉니다. (만약 알레르기의 개수와 선택한 음식의 개수가 같다면, 하나도 못먹는경우이므로 실패입니다.) 
					if(friend[i].notEatList.get(k) == foodList.get(j)) {
						allergeCnt += 1;
					}
				}
				
			}
			if(allergeCnt == foodList.size()) {
				return false;
			}
		}
		return true;
	}
	
	
}
class Friend{
	ArrayList<Integer> notEatList = new ArrayList<Integer>();
	public Friend() {
		
	}
}