백준 1062 (가르침)

문제

---

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

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

 

 

 

 

 

 

풀이

---

String 으로 분류 했지만, 문제 자체는 백트레킹을 이용한 문제다.

백트레킹은 값을 뒤로 가면서 찾는 방식 즉, BFS와 DFS 에서 주로 사용하는 방식이다.

 

DFS방식으로 문제를 풀었다.

최선의 방식을 찾을 때, 모든 선택하는 방법을 다 시도한 뒤 최대값을 찾으면 된다.

당연한 소리 같지만 코딩에서 자주 등장하는 풀이 방식이다.

 

visited[] 배열을 26개 만들어서 알파벳이 선택되었는지 아닌지를 판단한다.

 

이문제에서는 "anta" "tica" 는 무조건 들어가므로 알파벳을 적어도 5개 이상 배워야 단어를 읽을 수 있다.

 

k < 5 인 경우는 무조건 답이 0 이 된다.

 

k = 26 인 경우는 모든 알파벳을 배워 무조건 답이 n 이 된다.

 

나머지에 대해 생각을 해주면 된다.

 

깊이 우선 탐색을 통해 문제를 풀었는데 밑의 코드를 보면서 설명하겠다.

static void dfs(int start, int count) {
	
	if(count == k) {
		int cnt = 0;
		for(int i = 0 ; i < n ; i++) {
			boolean isTrue = true;
			
			for(int j = 0 ; j < subString[i].length(); j++) {
				if(!visited[subString[i].charAt(j) - 'a']) {
					isTrue = false;
					break;
				}
			}
			if(isTrue) {
				cnt++;
			}
		}
		
		max = Math.max(max, cnt);
		return;
	}
	
	for(int i = start ; i < 26 ; i++) {
		if(!visited[i]) {
			visited[i] = true;
			dfs(i + 1, count+1);
			visited[i] = false;
		}
	}
}

 

선택 된 알파벳의 갯수가 k 개가 되면(여기서 k는 acint 의 개수인 5를 뺀 k-5 상태다.) 지금까지 선택 된 알파벳을 가지고 읽을 수 있는 단어가 몇개인지를 확인한다.

 

k개가 되기 전에는 아직 선택되지 않은 알파벳을 선택하여 DFS를 재귀적으로 들어간다.

 

미리 a c i n t 를 선택 하는 코드다.

visited['a' - 'a'] = true;
visited['c' - 'a'] = true;
visited['i' - 'a'] = true;
visited['n' - 'a'] = true;
visited['t' - 'a'] = true;

 

 

<전체코드>

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

public class Main {	
	static StringBuilder sb = new StringBuilder();
	

	static String[] subString;
	static boolean[] visited = new boolean[26];
	static int max;
	static int k;
	static int n;
	
	public static void main(String[] args) throws IOException{
		
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
		n = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		
		if(k < 5) {
			System.out.println(0);
			return;
		}
		else if(k == 26) {
			System.out.println(n);
			return;
		}
		
		subString = new String[n];
		for(int i = 0 ; i < n ; i++) {
			String words = bufferedReader.readLine();
			subString[i] = words.substring(4, words.length() - 4);
		}
		
		k -= 5;
		visited['a' - 'a'] = true;
		visited['c' - 'a'] = true;
		visited['i' - 'a'] = true;
		visited['n' - 'a'] = true;
		visited['t' - 'a'] = true;
		
		dfs(0, 0);
		
		System.out.println(max);
		
		
	}
	
	static void dfs(int start, int count) {
		
		if(count == k) {
			int cnt = 0;
			for(int i = 0 ; i < n ; i++) {
				boolean isTrue = true;
				
				for(int j = 0 ; j < subString[i].length(); j++) {
					if(!visited[subString[i].charAt(j) - 'a']) {
						isTrue = false;
						break;
					}
				}
				if(isTrue) {
					cnt++;
				}
			}
			
			max = Math.max(max, cnt);
			return;
		}
		
		for(int i = start ; i < 26 ; i++) {
			if(!visited[i]) {
				visited[i] = true;
				dfs(i + 1, count+1);
				visited[i] = false;
			}
		}
	}
	
}