[BOJ / Java] 1062 - 가르침 (DFS + BackTracking)

삼성 SW 기출문제

백트래킹(BackTracking)으로 푸는 문제이다. 로직을 세우는 것의 중요함을 느꼈다.

1062번: 가르침

아직 실력이 부족해 이해하는 데에 많은 시간이 걸린 문제입니다.

저처럼 어려움을 겪으시는 분들께 도움이 되길 바라는 마음으로 기록합니다.

 

풀이

1. 모든 단어에는 'antic'이 들어간다. replaceAll 메소드를 사용해 잘라낸다.

2. 학습해야 하는 단어들은 words [String 배열]에 넣는다.

3. 배운 단어들을 비교하기 위해 studied [boolean 배열]을 생성한 뒤, antic을 true(배웠음)로 체크한다.

4. 예외처리를 먼저 해 준다. K(배울 수 있는 단어의 수)가 5보다 작으면 모든 단어를 배울 수 없으니 0을 출력, K가 26과 같으면 모든 단어를 출력할 수 있으니 N개만큼 출력한다.

5. 배울 수 있는 문자의 수를 계산하기 위한 변수 studiedCount는 기본적으로 antic이 들어가 있다. 따라서 5로 설정한다.

6. 반복문을 돌려 아직 학습하지 않은 알파벳에 한해 dfs를 돌린다.

7. 완전탐색으로 학습에 따른 결과를 계산한다.

- 가장 이해하기 어려웠던 부분. 하지만 이해하고 나니 쉬웠다.

- K가 6일 때 : 'b'를 학습하고 난 뒤, 'b'를 다시 학습하지 않았다고 돌려 놓고 다음 단어인 'd'를 학습한다. (#단어 탐색1)

- K가 7일 때 : 'b'를 학습하고, 더 배울 수 있는 단어가 남았기에 for문을 돌린다. 'b' 가 true(배운 상태)이며, 이미 배운 것 'b'를 제외한 'd'부터 'z'까지 한바퀴 쭉 돌면서 가장 큰 result를 찾는다. 각각의 dfs가 끝날 때마다 'b' 다음으로 배운 알파벳들은 false(배우지 않은 상태)로 돌리면서 계속 학습해 본다.(#단어 탐색2) for문이 끝나면, 'b'도 다시 학습하지 않은 상태로 되돌리고, #단어 탐색1 로 돌아간다.

 

메서드에서 for문을 돌리는 부분에 int i=index+1이므로, 계산해야 하는 경우의 수가 1씩 줄어드는 것을 알 수 있다.
즉, 시간 복잡도는 O(N!)이다.

 

8. studyWords를 사용해 어떤 알파벳을 배웠을 때 몇 개의 단어를 학습할 수 있는지 결과를 구한다.

 

문제의 입력 기준, 로그를 찍어 보면 'r'을 배울 때 가장 많은 단어(2개)를 학습할 수 있다는 것을 알 수 있다.

import java.util.*;

public class Main {
	
	static int N, K;
	static String[] words;
	static boolean[] studied;
	static int studiedCount = 0;
	static int result = 0;
	static int test = 0;
	
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		K = sc.nextInt();
		
		words = new String[N];
		
		for (int i=0; i<N; i++) {
			// antic은 생각할 필요가 없으므로 삭제
			words[i] = sc.next().replaceAll("[antic]", "");
		}
		
		studied = new boolean[26]; // 알파벳 전체에 해당하는 배열 생성
		studied['a' - 'a'] = true; // antic 은 배웠으므로 true로 체크
		studied['n' - 'a'] = true;
		studied['t' - 'a'] = true;
		studied['i' - 'a'] = true;
		studied['c' - 'a'] = true;
		
		// 배울 수 있는 글자가 5보다 작다면 당연히 결과는 0
		if (K<5) {
			System.out.println(0);
			return;
		// 배울 수 있는 글자가 26개라면 모든 단어 학습이 가능
		} else if (K==26) {
			System.out.println(N);
			return;
		}
		
		// 학습한 문자에 기본적으로 antic 5글자는 들어가 있음
		studiedCount = 5;
		// 일차적으로 결과를 뽑는다. 
		result = studyWords();
		// #단어 탐색 1
		for (int i=0; i<26; i++) {
			if (studied[i] == false) {
				dfs(i);
			}
		}
		System.out.println(result);
	}
	
	static void dfs(int index) {
		studied[index] = true; // 아직 공부하지 않은 글자에 한해서 dfs를 돌린다.
		studiedCount++;
		if (studiedCount == K) { // 공부 끝!
			result = Math.max(studyWords(), result);
		} else {
			// #단어 탐색 2
			for (int i=index+1; i<26; i++) {
				if (studied[i] == false) {
					dfs(i);
				}
			}
		}
		studied[index] = false; 
		studiedCount--;
		
	}
	
	static int studyWords() {
		int count = 0;
		for (int i=0; i<N; i++) {
			boolean isIn = true;
			String word = words[i];
			for (int j=0; j<word.length(); j++) {
				// 단어 중, 한 글자라도 배운적이 없으면 그 단어는 꽝
				if (studied[word.charAt(j) - 'a'] == false) {
					isIn = false;
					break;
				}
			}
			if (isIn == true) {
				count++;
			}
		}
		return count;
	}

}