[백준] 1062번: 가르침(완전 탐색, 백트래킹)

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

1062번: 가르침

코드

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

public class Main {
	static int N, K;
	static int max = 0;
	static boolean visit[] = new boolean[26];
	static String[] sArr;
	
	public static void dfs(int start, int count) {
		/*
		 * 기저사례: 주어진 K개 만큼 단어를 골랐을 때
		 * visit[]에 체크된 단어들과 비교해서 배울 수 있는 단어의 최댓값 구하기.
		 */
		if(count == K) {
			int num = 0;
			for(int i=0; i<sArr.length; i++) {
				boolean flag = true;
				for(int j=0; j<sArr[i].length(); j++) {
					
					/* K개를 골랐을 때, 고른 단어로 해당 문자열을 읽을 수 있는지 판단 */
					if(!visit[sArr[i].charAt(j) - 97]) {
						flag = false;
						break;
					}
				}
				if(flag)	num ++;
			}
			max = Math.max(max, num);
			return;
		}
		
		// 아직 K개를 배우지 않은 경우 -> 완전 탐색(알파벳 갯수: 26개)
		for(int i=start; i<26; i++) {
			if(!visit[i]) {
				visit[i] = true;
				dfs(i, count + 1);
				visit[i] = false;
			}
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		sArr = new String[N];
		//char[] checkWords = {'a', 'n', 't', 'i', 'c'};
		
		// 모든 단어는 "anta-'로 시작하고, "-tica"로 끝남. a n t i c
		if(K<5) {
			System.out.println("0");
			return;
		}
		
		// 알파벳 = 26개이므로 26이면 모두 읽을 수 있음.
		else if(K==26) {
			System.out.println(N);
			return;
		}
		else {
			// 접두사 anta 와 접미사 tica 제거.
			for(int i=0; i<N; i++) {
				String str = bf.readLine();
				sArr[i] = str.substring(4, str.length()-4);
			}
			
			// a n t i c 5개의 단어는 반드시 포함해야 하므로 -5
			K -= 5;
			
			// a n t i c -> 방문 체크
			visit['a' - 97] = true;
			visit['n' - 97] = true;
			visit['t' - 97] = true;
			visit['i' - 97] = true;
			visit['c' - 97] = true;
			
			// 재귀 + 백트래킹을 통해 최대 읽을 수 있는 단어 찾기
			dfs(0, 0);
			System.out.println(max);
		}
		
		bf.close();
	}

}

풀이

골드 문제 였지만 나름 짧아 보여서 덥썩 물었는데.. 너무 어려웠다 ........................................................

 

문제를 보면 N개의 단어 중 K개의 단어 만큼 글자를 학생들에게 가르치고, 학생들이 배운 K개의 단어로 읽을 수 있는 최댓값을 구해야 한다.

남극언어의 모든 단어는 "anta" 로 시작하고, "tica"로 끝난다.

즉 위 8개중 중복되는 단어는 a n t i c 이다.

따라서 주어진 K가 5개보다 작으면 어떠한 단어를 가르치더라도 아무 단어도 읽을 수 없다. => 0 출력

반대로 만약 주어진 K가 26이라면 ? => 알파벳은 26까지다. 따라서 모든 단어를 읽을 수 있다. => N 출력

이제 5개 ~ 26개 사이를 생각해 봐야 한다.

여기서는 배우지 않은 모든 단어들에 대해 완전 탐색 + 백트래킹을 통해 가장 많이 읽을 수 있는 단어를 찾는다.

 

먼저 모든 단어에는 anta, tica가 포함되어 있으므로 접두사 "anta"와 접미사 "tica"는 제거한다.

그럼 여기서 학생들에게 a n t i c 5개의 단어를 가르친 셈이다. 따라서 K의 값을 5만큼 뺀다.

여기서 배웠거나, 배우지 못한 알파벳들을 표시하기 위해 boolean[] visit 라는 배열을 선언했는데,.

만약 a를 배웠다면 => visit[0] = true로, c를 배웠다면 visit[2] = true로

알파벳을 숫자로 매칭시켜서(97을 빼면 된다. 아스키코드) 해당 인덱스의 값을 true로 바꿔주었다.

a n t i c 이 5개의 알파벳은 무조건 가르쳐야 하므로, 기본 true로 설정해줘야 한다.

그럼 각각 visit[0] = visit[13] = visit[19] = visit[8] = visit[2] = true 가 기본 베이스다.

 

그 다음으로, 알파벳에서 K-5개의 알파벳을 조합으로 뽑아줘야 한다.(순서는 상관없다.)

a b c 를 알던 b a c 를 알던 읽을 수 있는 단어는 똑같기 때문에, 순서의 의미가 없다.

 

재귀호출을 통해 K개만큼 골랐다면, 읽을 수 있는 단어를 카운트 해야 한다.

만약 "abcde"라는 단어가 있다고 가정하면, a~e까지 5개의 문자를 반복하면서 

현재 그 문자를 인덱스로 하는 visit[] 배열이 false로 설정되어 있다면, 그 단어는 배우지 않은 단어다.

따라서 뒤에는 더 볼필요없이 false로 설정하고 for문을 탈출하면 된다.

만약 모든 단어("abcde")를 탐색했는데, 모든 visit[] 배열이 true라면 ? 

그 단어는 읽을 수 있는 단어이므로, ++해준다.

그 후 이전에 K개를 골랐을때, 읽을 수 있는 단어와 비교해 최댓값을 찾는다.

 

 

 

너무 어렵다 ........ 아직 순열과 조합, 재귀, 백트래킹 에 대한 개념도 부족하고 이해도 부족하다...

머릿속으로 아무리 이해하려고 해도 잘 안되고 외우는 것 같다 ......

주말이나 다음주내로 시간내서 순열 조합 완전탐색에 대해 정리를 한번 해야할 것 같다..