문제

씬디는 애너그램(anagram) 프로그램을 만들어 줄 수 있는 남자를 좋아한다. 참고로 씬디는 매우 예쁘다.

애너그램 프로그램이란, 입력받은 영단어의 철자들로 만들 수 있는 모든 단어를 출력하는 것이다. 가령 "abc" 를 입력받았다면, "abc", "acb", "bac", "bca", "cab", "cba" 를 출력해야 한다.

입력받은 단어내에 몇몇 철자가 중복될 수 있다. 이 경우 같은 단어가 여러 번 만들어 질 수 있는데, 한 번만 출력해야 한다. 또한 출력할 때에 알파벳 순서로 출력해야 한다.

입력
첫째 줄에 단어의 개수 N 이, 둘째 줄부터 N개의 영단어가 들어온다. 영단어는 소문자로 이루어져 있다. 단어의 길이는 20보다 작거나 같고, 애너그램의 수가 100,000개 이하인 단어만 입력으로 주어진다.

출력
N개의 영단어에 대한 모든 가능한 애너그램을 출력한다. 각각의 영단어에 대한 애너그램을 출력할 때, 알파벳 순서로 중복되지 않게 출력한다.

6443번: 애너그램

풀이

이 문제는 사실 N과 M(10)문제와 비슷하다.

알파벳 순서로 출력하기 위해 각 알파벳을 DFS로 탐색하고 그 순서를 저장한다.
DFS의 depth를 매개변수로 넘겨주며 DFS 탐색 깊이가 주어진 문자열의 길이와 같아지면 DFS를 종료한다.

이때 같은 알파벳이 한 문자열에 두개 이상 주어질 수 있는데, 중복을 제거해야한다.
예를 들어 "abbc" 문자열이 주어졌을 때 'b'로 생길 수 있는 중복을 제거하기 위해
ab 로 시작하는 모든 문자열을 DFS로 구했다면 그 다음 DFS는 ab가 아닌 바로 ac로 넘어가야 한다.
그러기 위해서 pre라는 변수를 만들어서 이전 반복에서 같은 depth에서 사용된 문자가 현재 사용할 문자와 같다면 현재 문자는 DFS를 돌지 않고 다음 반복문으로 넘어간다.

코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int n;
string answer;
vector<bool> visited;


void dfs(int depth, int length, string& str){
    if (depth == length) {
        cout << answer << "\n";
        return;
    }
    
    char pre =' ';
    for (int i=0; i<str.size(); i++){
        if (visited[i] || str[i] == pre) continue;
        
        pre = str[i];
        visited[i] = true;
        answer.push_back(str[i]);
        dfs(depth+1, length, str);
        answer.pop_back();
        visited[i] = false;
    }
}

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);

    cin >> n;

    while (n--){
        string input;
        cin >> input;
        
        sort(input.begin(), input.end());
        visited.assign(input.size(), false );
        dfs(0, input.size(), input);
        answer.clear();
        input.clear();
    }

    return 0;
}

굳이 모든 경우를 일일히 구하지 않고 next_permutation()을 이용하여 해결하는 경우도 있다.