[백준 1342] 행운의 문자열 (C++)

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

문제

---

민식이와 준영이는 자기 방에서 문자열을 공부하고 있다. 민식이가 말하길 인접해 있는 모든 문자가 같지 않은 문자열을 행운의 문자열이라고 한다고 한다. 준영이는 문자열 S를 분석하기 시작했다. 준영이는 문자열 S에 나오는 문자를 재배치하면 서로 다른 행운의 문자열이 몇 개 나오는지 궁금해졌다. 만약 원래 문자열 S도 행운의 문자열이라면 그것도 개수에 포함한다.

 

입력

---

첫째 줄에 문자열 S가 주어진다. S의 길이는 최대 10이고, 알파벳 소문자로만 이루어져 있다.

 

출력

---

첫째 줄에 위치를 재배치해서 얻은 서로 다른 행운의 문자열의 개수를 출력한다.

 

문제 풀이

---

백트래킹 문제.

알파벳 별로 횟수를 저장한 후 백트래킹 함수를 이용해 사용할 수 있는 알파벳이 있다면 다음 깊이로 진행한다. 단, 문제 조건에 따라 이전 깊이(혹은 인덱스)에서 선택된 알파벳과 달라야 하므로 백트래킹 함수에 prev라는 매개변수를 추가하여, 해당 깊이의 알파벳과 이전 깊이의 알파벳과 비교한다.

 

아래는 코드.

#include <iostream>
#include <algorithm>
using namespace std;
string str;
int N;
int* alphabets;
int answer = 0;

void backTracking(int depth, int prev)
{
	if (depth == N)
	{
		answer++;
	}
	else
	{
		for (int i = 0; i < 26; i++)
		{
			if (alphabets[i] != 0)
			{
				if (depth == 0)
				{
					alphabets[i]--;
					backTracking(depth + 1, i);
					alphabets[i]++;
				}
				else
				{
					if (i != prev)
					{
						alphabets[i]--;
						backTracking(depth + 1, i);
						alphabets[i]++;
					}
				}
			}
		}
	}
}

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	cin >> str;
	N = str.length();
	alphabets = new int[26];
	for (int i = 0; i < 26; i++)
	{
		alphabets[i] = 0;
	}
	for (int i = 0; i < N; i++)
	{
		int index = str.at(i) - 97;
		alphabets[index]++;
	}
	backTracking(0, -1);
	cout << answer << "\n";
	return 0;
}