[6443] 애너그램

문제 링크 : https://www.acmicpc.net/problem/6443

6443 - 애너그램

본문

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

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

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

입력

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

출력

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

제한

시간 제한	메모리 제한
1sec	128MB

---

풀이

애너그램은 거의 무조건 백트래킹 방법을 사용하면 쉽게 구현할 수 있다. 이 문제 또한 백트래킹을 구현할 줄 안다면 쉽게 구현할 수 있다.

백트래킹에 대한 설명은 아래의 참고 알고리즘을 이용하자.

• 참고 알고리즘 : DFS-백트래킹

코드

사용 언어 : C

최종 수정일 : 2023 / 2 / 1

#include <stdio.h>

#define MAX_LEN 20
int alpha['z' - 'a' + 1];
char input[MAX_LEN + 1];
char making[MAX_LEN + 1];
int len;

#define getIndex(x) ((x) - ('a'))

void init() {
    for (int i = 0; i < 26; ++i) {
        alpha[i] = 0;
    }
    return;
}
void alphabetCount() {
    for (len = 0; input[len] != '\0'; ++len) {
        ++alpha[getIndex(input[len])];
    }
    making[len] = '\0';
    return;
}

void backtrack(int x) {
    if (x == len) {
        printf("%s\n", making);
        return;
    }

    for (int i = 0; i < 26; ++i) {
        if (alpha[i] > 0) {
            --alpha[i];
            making[x] = i + 'a';
            backtrack(x + 1);

            ++alpha[i];
        }
    }
    return;
}

int main() {
    int t;
    scanf("%d", &t);

    while (t--) {
        init();
        scanf("%s", input);

        alphabetCount();
        backtrack(0);
    }
    return 0;
}

• alpha[] : 입력받은 문자열을 알파벳 단위로 쪼개서 기록