[JAVA] BOJ(백준) - 가르침 - 1062

문제내용

https://www.acmicpc.net/problem/1062

1062번: 가르침

남극에 사는 김지민 선생님은 학생들이 되도록이면 많은 단어를 읽을 수 있도록 하려고 한다. 그러나 지구온난화로 인해 얼음이 녹아서 곧 학교가 무너지기 때문에, 김지민은 K개의 글자를 가르칠 시간 밖에 없다. 김지민이 가르치고 난 후에는, 학생들은 그 K개의 글자로만 이루어진 단어만을 읽을 수 있다. 김지민은 어떤 K개의 글자를 가르쳐야 학생들이 읽을 수 있는 단어의 개수가 최대가 되는지 고민에 빠졌다.

남극언어의 모든 단어는 "anta"로 시작되고, "tica"로 끝난다. 남극언어에 단어는 N개 밖에 없다고 가정한다. 학생들이 읽을 수 있는 단어의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문자로만 이루어져 있고, 길이가 8보다 크거나 같고, 15보다 작거나 같다. 모든 단어는 중복되지 않는다.

출력

첫째 줄에 김지민이 K개의 글자를 가르칠 때, 학생들이 읽을 수 있는 단어 개수의 최댓값을 출력한다.

---

문제 접근 방법

이번 문제는 백트래킹을 활용해 풀었고, 백트래킹이 뭔지 안다는 전제하에 로직을 풀이해 보겠다.

기본적인 로직은 'a'~'z'까지 알파벳을 배울수 있는 개수 만큼 조합을 만들어준다. 이때 백트래킹을 통해 모든 조합의 경우를 고려한다.
알파벳을 다 배웠을때 마다 읽을수 있는 단어의 개수를 세주고 최댓값을 갱신해주면 된다.

로직

1. 방문배열
   백트래킹을 활용할 것이기 때문에 방문배열이 필요하다. 이때 방문배열은 어떤 알파벳을 배웠는지 체크하는 역할이다.
   또한 "anta" , "tica"는 무조건 들어가는 단어이기 때문에 초기에 a n t i c 는 방문처리해준다.
   
   
2. 배울수 있는 알파벳 개수
   입력받은 k가 5개보다 작으면 "anta" 와 "tica"를 읽지 못하기 때문에 0을 출력
   입력받은 k가 26개보다 크거나 같으면 알파벳 전부를 배울수 있어서 모든 단어를 읽을 수 있다. 따라서 n을 출력.
   그외의 경우엔 백트래킹을 실행.
   
   
3. 백트래킹
   k가 6~25 사이일 경우 백트래킹을 통해 알파벳의 모든 조합을 확인한다.
   이때 종료조건은 알파벳을 배울수 있을만큼 다 배웠을때 즉, k만큼 배웠을때 읽을수 있는 단어의 개수를 세고 종료해준다.
   
   백트래킹의 매개변수는
   알파벳 몇개를 배웠는지 확인 시켜줄 depth변수,
   이미 배운 알파벳을 다시 확인할 필요가 없기 때문에 어떤 알파벳부터 탐색을 시작할지 알려줄 idx변수를 활용한다.

코드를 보고 생각해보자.

---

풀이

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

public class Main {
	static int n, k, k1;
	static int answer = Integer.MIN_VALUE; //정답(최댓값)
	static boolean[] check; //방문배열
	static String[] arr;
	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()); //단어 개수
		k = Integer.parseInt(st.nextToken()); //가르침 가능한 글자 수
		k1 = k-5; //a n t i c 를 제외하고 가르칠수 있는 글자 수
		arr = new String[n]; //"anta"와 "tica"를 제외하고 입력받은 단어들.
		
		//arr배열에 입력단어 넣기
		for(int i=0; i<n; i++) {
			st = new StringTokenizer(br.readLine());
			String str = st.nextToken();
			str = str.substring(4, str.length()-4);
			arr[i] = str;
		}
		
		if(k1<0) {
			System.out.println(0);
			System.exit(0);
		}else if(k1>=21) {
			System.out.println(n);
			System.exit(0);
		}
		
		initCheck(); //방문배열 초기값 설정, a n t i c 방문처리.
		backTracking(1,0); //배울수 있는 알파벳들 조합하기
		System.out.println(answer);
		
	}
	
	//매개변수-> idx:탐색을 시작할 알파벳, depth:배운 알파벳 개수
	public static void backTracking(int idx, int depth) {
		//배울수 있을만큼 알파벳 배웠으면 읽을수 있는단어 몇개인지 세기
		//종료조건
		if(depth == k1) {
			countWords(); 
			return;
		}
		
		//'a'부터 시작해서 'z'까지 백트래킹으로 배울수 있는 알파벳 조합을 만듦.
		for(int i=idx; i<check.length; i++) {
			if(check[i]) continue;
			check[i] = true;
			backTracking(i, depth+1);
			check[i] = false;
		}
	}
	
	//읽을수 있는 단어 세기
	public static void countWords() {
		int cnt = 0;//읽을수 있는 단어 개수
		
		//단어 하나마다 읽을수 있는지 없는지 체크
		for(int i=0; i<arr.length; i++) {
			int w = 0;
			char[] word = arr[i].toCharArray();
			for(int j=0; j<word.length; j++) {
				if(!check[word[j]-96]) {//알파벳 안배워서 못읽음
					w = -1;
					break;
				}
			}
			
			if(w!=-1) cnt++;
		}
		
		//최댓값 갱신
		answer = Math.max(answer, cnt);
	}
	
	//a n t i c 방문 표시
	public static void initCheck() {
		//'a'= 1 , 'b'=2 ... 'z'=26
		check = new boolean[27];
		check['a'-96] = true;
		check['n'-96] = true;
		check['t'-96] = true;
		check['i'-96] = true;
		check['c'-96] = true;
	}
}

---

마치며

해당 문제는 비트마스크 라는 알고리즘으로 풀수 있다고 한다. 비트마스크를 활용한다면 좀더 효율적으로 풀수 있다고 하는데 비트마스크에 대해 알아봐도 좋을 것 같다.