[백준] 1342 행운의 문자열 - 백트래킹(Backtracking) + DFS(깊이우선탐색) + 시간초과(Timeout) JAVA

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

1342번: 행운의 문자열

코드설명

백트래킹(Backtracking) + DFS(깊이우선탐색) + 시간초과(Timeout) 를 활용하는 문제입니다.

 

주어진 문자열을 모두 순열로 배치하여 완전탐색하면서 만약 행운의 문자열일경우 ( 인접해 있는 모든 문자가 같지않을경우 )에만 계속해서 진행하면 됩니다.

 

또한, 추가적인 문제에서의 Skill은, alphabet[26] 배열 을 활용하여서 진행하는것이다.

이를 통해 훨씬 쉽게 주어진 알파벳들을 가지고서 완전탐색할 수 있습니다.

 

코드로직입니다.

1. DFS(깊이 우선 탐색)를 이용하여 단어를 만들 수 있는 경우의 수를 탐색합니다.
2. DFS 함수에서 각 위치(level)에 대해 현재 사용 가능한 알파벳을 확인하고, 이전 위치의 알파벳과 중복되지 않도록 처리합니다.
3. 모든 알파벳을 사용하여 단어를 만들었을 때(level == answer.length), 경우의 수를 증가시킵니다.

 

코드

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

public class Main {
	public static int N, M, K ;
	public static int cnt = 0;
	public static int[] alphabet = new int[26];
	public static int[] answer;
	public static boolean[] visited;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());

    	String str = st.nextToken();
    	answer = new int[str.length()];
    	for(int i=0;i<str.length();i++) {
    		alphabet[str.charAt(i) - 'a'] += 1;
    	}
    	dfs(0);
    	
    	System.out.println(cnt);
    }
    
    public static void dfs(int level) {
    	if(level == answer.length) {
    		cnt += 1;
    		return ;
    	}
    	
    	for(int i=0;i<26;i++) {
    		if(alphabet[i] > 0) {
    			alphabet[i] -= 1;
    			
    			if(level == 0) {
    				answer[level] = i;
    				dfs(level + 1);
    			}
    			else {
    				if(i == answer[level - 1]) {
        				
        			}
        			else if(i != answer[level - 1]) {
        				answer[level] = i;	
        				dfs(level + 1);
        			}	
    			}
    			
    			alphabet[i] += 1;
    		}
    	}
    	
    }
}