[Java] 백준 1497번 : 기타콘서트

문제

강토는 Day Of Mourning의 기타리스트로, 다가오는 공연을 준비하고 있다.

어느 날 강토의 집에 도둑이 들어서 기타를 모두 도둑맞고 말았다. 기타를 사야 한다.

강토는 공연 때 연주할 노래의 목록을 뽑아 놓았다. 하지만, 하나의 기타로 모든 곡을 연주할 수는 없다. 어떤 기타는 어떤 곡을 연주할 때, 이상한 소리가 나기 때문이다. 항상 완벽을 추구하는 강토는 이런 일을 용납하지 않는다.

최대한 많은 곡을 제대로 연주하려고 할 때, 필요한 기타의 최소 개수를 구하는 프로그램을 작성하시오.

예를 들어, GIBSON으로 1, 2, 3번 곡을 제대로 연주할 수 있고, FENDER로 1, 2, 5번 곡을 제대로 연주할 수 있고, EPIPHONE으로 4, 5번 곡을 제대로 연주할 수 있고, ESP로 1번곡을 제대로 연주할 수 있다면, 세준이는 EPIPHONE과 GIBSON을 사면 최소의 개수로 모든 곡을 연주할 수 있다. 

입력

첫째 줄에 기타의 개수 N과 곡의 개수 M이 주어진다. N은 10보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 기타의 이름과 기타가 연주할 수 있는 곡의 정보가 1번 곡부터 차례대로 주어진다. Y는 연주할 수 있는 것이고, N은 없는 것이다. 기타의 이름은 알파벳 대문자로만 이루어져 있고, 길이는 2 이상, 50 이하이다. 두 기타의 이름이 같은 경우는 없다.

출력

첫째 줄에 필요한 기타의 개수를 출력한다. 만약 연주할 수 있는 곡이 없으면 -1을 출력한다.

예제 입력 1

4 5
GIBSON YYYNN
FENDER YYNNY
EPIPHONE NNNYY
ESP YNNNN

예제 출력 1

2

예제 입력 2

3 5
GIBSON YNYYN
FENDER NNNYY
TAYLOR YYYYY

예제 출력 2

1

예제 입력 3

3 2
AB YN
AA YN
BA NN

예제 출력 3

1

예제 입력 4

5 7
FENDER YYNNYNN
GIBSON YYYNYNN
CRAFTER NNNNNYY
EPIPHONE NNYNNNN
BCRICH NNNYNNN

예제 출력 4

3

예제 입력 5

2 25
GIBSON NNNNNNNNNNNNNNNNNNNNNNNNN
FENDER NNNNNNNNNNNNNNNNNNNNNNNNN

예제 출력 5

-1

 

소스코드

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {

	private static int N, M;
	private static String[] yon;
	private static int MIN_GUITAR=Integer.MAX_VALUE;
	private static int MAX_MUSIC=Integer.MIN_VALUE;
	
	public static void main(String[] args) {
		
		Scanner sc=new Scanner(System.in);
		N=sc.nextInt();
		M=sc.nextInt();
		String s=null;
		yon=new String[N];
		for(int i=0;i<N;i++) {
			s=sc.next();
			yon[i]=sc.next();
		}
		
		canPlay(N, new boolean[N]);	// 가능한 모든 부분집합을 완전 탐색하는 메서드
		System.out.println(MIN_GUITAR==0?-1:MIN_GUITAR);	// 연주할 수 있는 곡이 없으면 -1, 있으면 기타의 개수를 출력한다.
	}
	
	private static void canPlay(int toCheck, boolean[] checked) {	// toCheck : 탐색할 남은 원소의 개수, checked : 원소를 방문했는지 여부
		if(toCheck==0) {	// 탐색할 원소가 남지 않았으면, 현재 부분집합에서 필요한 기타의 개수와 연주할 수 있는 곡의 개수를 확인한다.
			checkMinGuitar(checked);
			return;
		}
		
		checked[checked.length-toCheck]=true;
		canPlay(toCheck-1, checked);	// 현재 원소를 포함하는 경우 재귀
		checked[checked.length-toCheck]=false;
		canPlay(toCheck-1, checked);	// 현재 원소를 포함하지 않는 경우 재귀
	}
	
	private static void checkMinGuitar(boolean[] checked) {	// checked : 부분집합에서 원소의 포함 여부
		int guitar=0;
		Set<Integer> musicSet=new HashSet<>();	// 같은 곡은 중복 저장하지 않도록 하기 위해 set으로 음악 포함 여부 확인
		for(int i=0;i<checked.length;i++) {
			if(checked[i]) {	// 원소를 포함하고 있는 경우, 기타의 개수를 1만큼 증가시키고, 해당 기타가 연주 가능한 곡의 번호를 musicSet에 저장
				guitar++;
				for(int j=0;j<yon[i].length();j++) {
					if(yon[i].charAt(j)=='Y') musicSet.add(j);
				}
			}
		}
		if(musicSet.size()>=MAX_MUSIC && guitar<MIN_GUITAR) {	// musicSet의 크기가 현재까지 연주 가능한 음악의 개수 이상일 때, 기타의 개수가 최소를 만족하면
			MIN_GUITAR=guitar;	// 최소 기타 개수 값 갱신
			MAX_MUSIC=musicSet.size();	// 최대 연주 가능한 음악의 수 갱신
		}
	}
}