[백준] 애너그램

과거에 풀었던 문제들을 복습하는겸 백트래킹 문제를 다시 풀어 보았다. 이 문제는 실버1 정도에 쉬운 문제지만 잘못하다가는 좀 헤맬수있는 루트에 빠질 수 있어서 문제를 기록하기로 결심했다.

평범하게 애너그램을 만들면 되는 문제고 알파벳 순으로 출력하면 된다. 다만! 이 문제를 조금더 복잡하게 만드는 요소는 바로 애너그램을 만들려고 하는 문자가 중복 되는 캐릭터로 이루어져있단 것이다.

단순하게 'abc' 라면 일반적인 permutation 방식으로 애너그램을 쉽게 만들 수 있지만 acba 같이 중복되는 알파벳이 있다면은 aabc 를 만들 수 있어도 뒤에 똑같은 a에서 계산을 해줄때 aabc를 다시 한번 만드는 불상사가 있을것이다.

그래도 답을 억지로라도 출력할 수 있는 방법은 존재한다. Map을 이용해서 만약에 등록된 단어면 출력하지 않고 처음보는 단어면 출력하게 된다면은 중복 없이 답을 낼수 있었을것이다.

void dfs(string& s, vector<bool>& visited, string tmp){
    if(tmp.length() == s.length()){
        if(!hashMap.count(tmp)) cout << tmp << endl; 
        hashMap[tmp]++; 
        return; 
    }

    for(int i = 0; i < s.length(); i++){
        if(!visited[i]){
            visited[i] = true; 
            tmp += s[i]; 
            dfs(s,visited,tmp);
            tmp.pop_back();
            visited[i] = false; 
        }
    }
}

그러나 이 방법은 결국 모든 조합을 다시한번 돌리는거기 때문에 aaaaaaa같은 상황이면 정말로 많은 dfs를 돌렸을것이다.

그렇기 때문에 여기서 나오는 2가지 초이스는

1. 알파벳 포지션으로 dfs 돌리기
2. 알파벳별로 dfs 돌리기

첫번쨰 선택지가 내가 했던 visited[i] 방식으로 포지션 별로 dfs 를 돌린거지만 이 문제는 중복이 허용되기때문에 사실 알파벳 별로 dfs 를 돌린다면은 순서 보장과 함께 바로바로 다음 알파벳으로 넘어가서 쓸데없는 계산을 줄일수 있을것이다.

#include <iostream> 
#include <bits/stdc++.h> 
#define endl "\n"
#define MAX 100010
using namespace std;

int N; 
vector<string> anagrams; 
int alphabets[26]; 

void Input(){
    cin >> N; 
    for(int i = 0; i < N; i++){
        string s; 
        cin >> s; 
        anagrams.push_back(s); 
    }
}

void dfs(string& s, string tmp){
    if(tmp.length() == s.length()){
        cout << tmp << endl; 
        return; 
    }

    for(int i = 0; i < 26; i++){
        if(alphabets[i] > 0){
            alphabets[i]--;
            tmp += (char)('a' + i); 
            dfs(s,tmp);
            alphabets[i]++;
            tmp.pop_back(); 
        }
    }
}

void Solution(){
    for(int i = 0; i < anagrams.size(); i++){
        memset(alphabets,0,sizeof(alphabets)); 
        for(char& c : anagrams[i]) alphabets[c - 'a']++; 
        dfs(anagrams[i],""); 
    }
}


void Solve(){
    Input();
    Solution(); 
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen("input.txt", "r", stdin);
    Solve();
    return 0;

}