BEAKJOON / 백준 - JAVA 1497번 기타콘서트

2024.09.04기준 - 실버1

728x90

백준, BEAKJOON, BOJ, JAVA, 자바

 

풀이

이 문제는 최대한 많은 곡을 칠 때, 가장 적은 기타의 사용 횟수를 출력하는 문제입니다.

 

문제 설명

최대한 많은 곡을 치는 문제이기 때문에 무조건 모든 곡을 칠 수 있어야되는게 아니라 적어도 1곡 이상을 친다면 기타의 개수를 출력해야 되는 것이 포인트라고 생각합니다.

 

1. 입력받은 기타와 기타가 칠 수 있는 곡의 여부를 저장합니다.

기타의 이름은 필요가 없다고 판단하여 이름은 따로 저장하지 않도록 했습니다.

(문제에서 중복되는 기타는 없다고 했기 때문에 인덱스로만 계산을 해도 상관없다고 생각했습니다.)

arr = new boolean[n][m]; // 기타로 칠 수 있는 곡을 저장하는 배열
visit = new boolean[n]; // 기타 사용 여부

char[] str;
for (int i = 0; i < n; i++) {
    st = new StringTokenizer(br.readLine());
    st.nextElement();
    str = st.nextToken().toCharArray();

    for (int j = 0; j < m; j++) {
        if (str[j] == 'Y') {
            arr[i][j] = true;
        }
    }
}

 

2. 먼저 탐색을 하기 전에 필요한 함수들을 생성했습니다.

- 모든 곡을 칠 수 있는지 여부를 반환하는 함수를 생성.

- 현재 사용하는 기타로 몇개의 곡을 칠 수 있는지 반환하는 함수 생성.

- 현재 사용하는 기타들의 곡 여부를 반환하는 함수 생성.

// 현재 사용하는 기타들의 곡 여부를 반환하는 함수.
private static boolean[] beginCheck() {
    boolean[] result = new boolean[m];

    for (int i = 0; i < n; i++) {
        if (visit[i]) {
            for (int j = 0; j < m; j++) {
                if (arr[i][j]) {
                    result[j] = true;
                }
            }
        }
    }

    return result;
}

// 현재 기타로 몇개의 곡을 칠 수 있는지 반환하는 함수.
private static int numcheck(boolean[] vi) {
    int num = 0;

    for (int i = 0; i < m; i++) {
        if (vi[i]) {
            num++;
        }
    }

    return num;
}

// 모든 곡을 칠 수 있는지 여부를 반환하는 함수.
private static boolean check(boolean[] vi) {
    for (int i = 0; i < m; i++) {
        if (!vi[i]) {
            return false;
        }
    }

    return true;
}

 

3. 위에 함수들을 이용해 탐색을 하는 함수를 생성합니다.

무조건 모든 곡을 치는게 아니기 때문에 모든 곡을 치지 않았다면 현재 곡의 개수와 사용한 기타의 개수를 함수를 돌 때 마다 저장을 해주면서 모든 곡이 들어오면 함수가 종료되게 설계를 했습니다.

if (check(vi)) { // 모든 곡을 칠 수 있다면 가장 작은 기타를 사용한걸 저장.
    min = Math.min(min, count);
    return;
} else { // 모든 곡은 아니지만 1곡 이상 칠 수 있다면 저장.
    int num = numcheck(vi);

    // 현재 칠 수 있는 곡보다 많다면
    if (song < num) {
        song = num;
        songmin = count;

    // 현재 칠 수 있는 곡이랑 같지만 더 적은 기타를 사용한다면
    } else if (song == num && songmin > count) {
        songmin = count;
    }
}

 

모든 경우의 수를 계산하는 반복문을 생성해 함수를 재귀하면서 계산을 진행했습니다.

1. 치지 않은 기타라면 조건문에 들어와 사용여부를 체크해주면서 그 기타가 칠 수 있는 곡을 체크해주었습니다.

2. 그렇게 체크된 변수를 가지고 다시 재귀를 합니다.

3. 재귀가 끝나 돌아오면 다시 사용여부를 false로 바꿔주면서 중복된 곡이 있을 수 있기 때문에 현재 사용하는 기타를 참조해 칠 수 있는 곡을 다시 저장해줍니다.

// 모든 경우의 수를 계산하는 반복문
for (int i = index + 1; i < n; i++) {
    if (!visit[i]) { // 치지 않은 기타라면
        visit[i] = true;

        // 이 기타의 칠 수 있는 곡 여부를 저장
        for (int j = 0; j < m; j++) {
            if (arr[i][j]) {
                vi[j] = true;
            }
        }

        bfs(vi, count + 1, i);

        // 나오면서 다시 기타를 사용하지 않는다고 저장.
        visit[i] = false;

        // 사용하지 않는 기타를 제외한 곡을 여부 저장
        vi = beginCheck();
    }
}

 

 

코드

package Main;

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

public class Main {
	
	static int n, m, sum, min = 11, song = 0, songmin = 11;
	static boolean[][] arr;
	static boolean[] visit;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken()); // 기타의 개수
		m = Integer.parseInt(st.nextToken()); // 곡의 개수
		
		arr = new boolean[n][m]; // 기타로 칠 수 있는 곡을 저장하는 배열
		visit = new boolean[n]; // 기타 사용 여부
		
		char[] str;
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			st.nextElement();
			str = st.nextToken().toCharArray();
			
			for (int j = 0; j < m; j++) {
				if (str[j] == 'Y') {
					arr[i][j] = true;
				}
			}
		}
		
		// 함수에서 사용할 현재 기타로 칠 수 있는 곡의 여부
		boolean[] vi = new boolean[m];
		bfs(vi, 0, -1);
		
		if (min == 11) { // 모든 곡을 못친다면
			if (songmin == 11 || songmin == 0) { // 1개의 곡도 못친다면 
				min = -1;
			} else { // 적어도 1개 이상의 곡을 칠 수 있다면
				min = songmin;
			}
		}
		
		bw.write(Integer.toString(min));
		bw.flush();
		bw.close();
		br.close();
	}
	
	private static void bfs(boolean[] vi, int count, int index) {
		if (check(vi)) { // 모든 곡을 칠 수 있다면 가장 작은 기타를 사용한걸 저장.
			min = Math.min(min, count);
			return;
		} else { // 모든 곡은 아니지만 1곡 이상 칠 수 있다면 저장.
			int num = numcheck(vi);
			
			// 현재 칠 수 있는 곡보다 많다면
			if (song < num) {
				song = num;
				songmin = count;
				
			// 현재 칠 수 있는 곡이랑 같지만 더 적은 기타를 사용한다면
			} else if (song == num && songmin > count) {
				songmin = count;
			}
		}
		
		// 모든 경우의 수를 계산하는 반복문
		for (int i = index + 1; i < n; i++) {
			if (!visit[i]) { // 치지 않은 기타라면
				visit[i] = true;
				
				// 이 기타의 칠 수 있는 곡 여부를 저장
				for (int j = 0; j < m; j++) {
					if (arr[i][j]) {
						vi[j] = true;
					}
				}
				
				bfs(vi, count + 1, i);
				
				// 나오면서 다시 기타를 사용하지 않는다고 저장.
				visit[i] = false;
				
				// 사용하지 않는 기타를 제외한 곡을 여부 저장
				vi = beginCheck();
			}
		}
	}
	
	// 현재 사용하는 기타들의 곡 여부를 반환하는 함수.
	private static boolean[] beginCheck() {
		boolean[] result = new boolean[m];
		
		for (int i = 0; i < n; i++) {
			if (visit[i]) {
				for (int j = 0; j < m; j++) {
					if (arr[i][j]) {
						result[j] = true;
					}
				}
			}
		}
		
		return result;
	}
	
	// 현재 기타로 몇개의 곡을 칠 수 있는지 반환하는 함수.
	private static int numcheck(boolean[] vi) {
		int num = 0;
		
		for (int i = 0; i < m; i++) {
			if (vi[i]) {
				num++;
			}
		}
		
		return num;
	}
	
	// 모든 곡을 칠 수 있는지 여부를 반환하는 함수.
	private static boolean check(boolean[] vi) {
		for (int i = 0; i < m; i++) {
			if (!vi[i]) {
				return false;
			}
		}
		
		return true;
	}
}