[Algorithm] boj_6443 (backtracking)

문제

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

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

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

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

입력

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

출력

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

---

접근 방법

• 알파벳을 입력받고 정렬해준다

  → 사전 순 출력
  

• 처음엔 백트래킹으로 모든 경우의 수를 구하고, 구할때마다 HashSet에 저장하여 중복을 제거하였지만, aaaaaaabbbcc 와 같은 경우 수많은 중복 문자열이 생성되고, 생성될때마다 루프를 반복해서 돌기 때문에 메모리 초과가 뜬다.

• 그래서, 같은 위치(depth)에서 같은 문자열이 사용될 경우, skip 하도록 해야한다.

  • prev를 초기화 시킴으로써 skip 하도록 할 수 있다.
  • 특정 알파벳을 사용하고 난 후 , 루프를 빠져나올때 prev를 해당 문자열로 초기화시키면, 루프를 빠져나가 같은 위치에 새로운 알파벳을 채울때 해당 문자열은 사용하지 않도록 하기 때문에 가능한 것이다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class boj_6443_backtracking {

    static int N;
    static boolean[] isUsed;
    static String[] alphabets;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        while (N --> 0) {
            alphabets = br.readLine().split("");

            //sort
            Arrays.sort(alphabets); //사전순 출력

            isUsed = new boolean[alphabets.length];
            makeWord(new StringBuilder());
        }

        System.out.println(sb);
    }

    static void makeWord(StringBuilder curWord) {
        if (curWord.length() == alphabets.length) {
            sb.append(curWord).append("\n");
            return;
        }

        String prev = ""; //이전에 사용한 문자 저장

        for (int i = 0; i < alphabets.length; i++) {
            if (isUsed[i]) continue;
            if (alphabets[i].equals(prev)) continue;

            isUsed[i] = true;
            curWord.append(alphabets[i]);
            makeWord(curWord);
            curWord.deleteCharAt(curWord.length() - 1);
            isUsed[i] = false;
            prev = alphabets[i];
        }
    }
}