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

passionfruit200 2024. 5. 15. 16:45

2024. 5. 15. 16:45

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

코드설명

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

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

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

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

테스트케이스

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

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

결과 1

코드

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() {
		
	}
}

'알고리즘 > algospot' 카테고리의 다른 글

[종만북] 선택정렬(Selection Sort)과 삽입정렬(Insertion Sort) - JAVA (0)	2024.05.15
[종만북] 가장 간단한 형태의 소인수 분해 알고리즘 - 완전탐색(BruteForce) JAVA (0)	2024.05.15
[종만북] 성형 전 사진 찾기 - 이진탐색(Binary Search) JAVA (0)	2024.05.15
[종만북] 다이어트 현황 파악 : 이동 평균 계산하기 - 슬라이딩 윈도우(Sliding Window) + 누적합(Prefix Sum) JAVA (0)	2024.05.15
[종만북] 신문기사의 오류 확인하기 ( 400m 달리기 ) - JAVA (0)	2024.05.12

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

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`

이 페이지의 URL 복사	`S` `S`
맨 위로 이동	`T` `T`
티스토리 홈 이동	`H` `H`
단축키 안내	`Shift` + `/` `⇧` + `/`

passionfruit200