[백준, Java] 1497번, 기타콘서트(백트래킹)

문제 링크

1497번: 기타콘서트

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

 

접근 방법

이 문제에 핵심

 

1. 각 기타는 연주할 수 있는 노래 목록이 존재합니다.

2. 각 기타의 이름이 다르며, 'Y'는 연주 가능함을 뜻하고, 'N'은 연주 불가능을 뜻합니다.

3. 가장 많이 연주할 수 있는 최소 기타 개수를 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 백트래킹을 통해서 가장 많이 연주할 수 있는 최소 기타 개수를 탐색합니다.

 

3. 가장 많이 연주할 수 있는 최소 기타 개수을 결과로 출력합니다.

 

 

비트마스킹 진행(연주 가능한 목록)

 

기타의 연주 가능 목록을 비트의 형태로 표현할 수 있습니다.

 

곡의 최대 개수가 50개이기 때문에 Long형에서 비트마스킹으로 모든 곡을 표현할 수 있습니다.

 

YYYNN : 11100

 

NNNYY : 00011

 

위에 연주 가능한 목록에 대해서 2개의 기타를 사용하게 된다면

 

OR연산을 진행합니다.

 

YYYNN(11100) |(OR) NNNYY(00011)  : YYYYY(11111)

 

→ 모든 곡을 연주할 수 있는 것을 확인할 수 있습니다.

 

백트래킹

 

백트래킹을 탐색할 때 선택할 수 있는경우는 2가지 있습니다.

 

 

1. 현재 가리키는 기타를 사용한 경우

 

OR연산을 통해서 연주 가능한 곡을 업데이트합니다.

 

2. 현재 가리키는 기타를 사용하지 않은 경우

 

OR연산을 진행하지 않고 다음 기타를 탐색합니다.

 

※ 모든 곡을 칠 수 있지만, 최소값이 아닌 경우에는 더 탐색을 진행해도 의미가 없기 때문에 탐색을 종료합니다.

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

N : 4

 

M : 5

 

 

기타	가능한 곡 목록
GIBSON	YYYNN(11100)
FENDER	YYNNY(11001)
EPIPHONE	NNNYY(00011)
ESP	YNNNN(10000)

 

 

 

2. 백트래킹을 통해서 가장 많이 연주할 수 있는 최소 기타 개수를 탐색합니다.

 

백트래킹 진행

 

 

GIBSON, FENDER 기타 사용

 

11100 | 11001 : 11101

 

GIBSON, FENDER, EPIPHONE 기타 사용

 

11100 | 11001 | 00011 : 11111

 

....

 

 

GIBSON, EPIPHONE  기타 사용

 

11100 | 00011 : 11111

 

 

3. 가장 많이 연주할 수 있는 최소 기타 개수을 결과로 출력합니다.

 

모든 곡을 연주 가능하면서, 2개의 기타를 사용한 경우가 존재

 

GIBSON, EPIPHONE  기타 사용

 

 

2을 결과로 출력 합니다.

 

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여  기타의 정보를 띄어쓰기 기준 저장합니다.
• 기타의 연주 가능 곡 목록에서 'Y' : 1, 'N' : 0으로 비트 형태로 변경하였습니다.
• search함수를 통해서 최대 곡 연주하는 경우에서 최소 기타 수를 구합니다.
• 탐색을 통해 얻은 최소 기타 수를 BufferedWriter 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

• search함수는 백트래킹을 통해서 기타 사용 여부의 경우를 나누어서 최대 곡 연주 개수의 최소 기타 개수를 탐색합니다.

결과코드

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    static int N, M, minGuitarCount = Integer.MAX_VALUE;
    static int max = 0;
    //기타 연주 가능 목록 비트마스킹 배열
    static long[] guitarBit;
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        guitarBit = new long[N];
        //입력값 저장
        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine()," ");
            st.nextToken();
            char[] guitarTF = st.nextToken().toCharArray();
            //'Y' = 1, 'N' = 0 비트 형태로 변경
            for(int j=0;j<M;j++){
                if (guitarTF[j] == 'Y') {
                    guitarBit[i] |= (1L<<j);
                }
            }
        }
        //백트래킹을 통해서 탐색 진행
        search(0,  0L, 0);
        //연주할 수 있는 곡이 없을 때
        if (minGuitarCount == 0) {
            minGuitarCount = -1;
        }
        //기타의 개수 BufferedWriter 저장
        bw.write(String.valueOf(minGuitarCount));
        bw.flush();
        bw.close();
        br.close();
    }
    //백트래킹을 통해서 기타 연주 여부를 기준으로 탐색합니다.
    static void search(int idx, long guitarMask, int val){
        //현재 연주 가능한 곡의 개수
        int bitCount = Long.bitCount(guitarMask);

       
        //현재 최대값은 같지만, 사용한 기타의 수가 더 작을 때
        if(bitCount == max && val < minGuitarCount) {
            minGuitarCount = val;
        }
        //현재 최대값보다 더 많은 곡을 칠 수 있을 때
        if(bitCount > max) {
            minGuitarCount = val;
            max = bitCount;
        }
        //모든 곡을 칠 때, 모든 기타를 확인했을 때
        if(bitCount == M || idx == N){
            return;
        }

        //현재 기타를 사용할 때
        search(idx+1, guitarMask | guitarBit[idx], val+1);
        //현재 기타를 사용하지 않을 때
        search(idx+1, guitarMask, val);

    }
}