[백준] 가르침 1062 - JAVA

문제

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

1062번: 가르침

 

풀이

간단하지만 간단하지 않은 백트레킹 문제였다. 

문제 풀이는 간단하다. 

 

1.  'a', 'n', 't', 'i', 'c' 먼저 방문 체크한다.

2.  백트레킹 하면서 'a', 'n', 't', 'i', 'c'를 제외한 문자에 대해 조합을 만든다.

3. 만들어진 문자열에 대해 단어의 문자가 있는지 체크한다.

 

이때, 백트레킹 할때 가지치기가 필요하다.

알파벳 순서대로 문자를 확인하기 때문에 그다음에 확인할 알파벳은 그 뒤 알파벳일것이다. 

따라서, 함수에 start 라는 알파벳을 어디서부터 확인할지 정해놓는 파라미터를 두어야 시간초과가 발상하지 않는다. 

 

코드

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

public class Main {	 

	static int n, k;
	static int visit [] = new int [26];
	static String strArr[];
	static int max = 0;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		
		strArr = new String[n];
		
		for(int i=0;i<n;i++) {
			strArr[i] = br.readLine();
			strArr[i].replace("anta", "");
			strArr[i].replace("tica", "");
			
		}
				
		visit['a' -'a'] = 1;
		visit['c' -'a'] = 1;
		visit['n' -'a'] = 1;
		visit['t' -'a'] = 1;
		visit['i' -'a'] = 1;
		
		back(0, 1);
		System.out.println(max);
	}
	
	static void back(int start, int idx) {
		if(idx == k-4) {
			int result=0;
			
			for(int i=0;i<n;i++) {
				boolean isread = true;
				for(char ch : strArr[i].toCharArray()) {
					if(visit[ch-'a'] == 0) {
						isread = false;
						break;
					}
				}
				if(isread) result++;
			}
			max = Math.max(max, result);
			return;
		}
		for(int i=start;i<26;i++) {			
			if(visit[i] == 0) {
				visit[i] = 1;
				back(i+1, idx+1);
				visit[i] = 0;
			}
			
		}		
	}
}