[백 트래킹, 브루트 포스] BOJ 1342 행운의 문자열

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

1342번: 행운의 문자열

 

문제 해결 알고리즘

 

전형적인 백트래킹 문제인데 거기에 인접해 있는 모든 문자가 같지 않은 문자열이라는 조건만 추가해준다.

 

 

소스 코드

 

#include <bits/stdc++.h>
using namespace std;

int arr[26];
int result = 0;
int N;

bool isTrue(string str){
	
	bool flag = true;
	
	for(int i=0;i<str.size()-1;i++){
		if(str[i] == str[i+1]) flag =false;
	}
	
	return flag;
}

void dfs(int pos, string str){
	
	if(pos == N){
		if(isTrue(str)){
			result ++;
		}
		
		return;
	}
	
	for(int i=0;i<26;i++){
		if(arr[i]) {
			str += char(i+'a');
		
			arr[i] --;
		
			dfs(pos+1, str);
		
			str = str.substr(0,str.length()-1);
			arr[i]++;
		}
	}
}

int main(){
	string str; cin >> str;
	N = str.size();
	
	for(int i=0;i<str.size();i++){
		arr[str[i] - 'a']++; 
	}
	
	dfs(0, "");
	
	cout << result;
}