암호 만들기 - 백준 1759 (Java)

 

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

 

풀이

해당하는 모든 경우에 대해 출력을 해야하므로 DFS 탐색으로 진행했다.

 

main()

static char[] alphabet;

//모음 리스트
static List<Character> vowelList = new ArrayList<>();
static boolean[] isUsed;

//최종 정답 기록하는 StringBuilder
static StringBuilder sb = new StringBuilder();

//중간중간 임시로 기록하는 StringBuilder
static StringBuilder tempSb = new StringBuilder();

public static void main(String[] args) throws IOException {
    //서로 다른 L개의 알파벳 소문자
    //최소 1개의 모음, 최소 2개의 자음
    //암호 내에서 증가하는 순서로 배열

    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

    StringTokenizer st = new StringTokenizer(bf.readLine());

    int length = Integer.parseInt(st.nextToken());
    int total = Integer.parseInt(st.nextToken());

    String str = bf.readLine().replaceAll(" ", "");
    int strLen = str.length();
    alphabet = new char[strLen];

    for (int i = 0; i < strLen; i++) {
        char c = str.charAt(i);

        //alphabet 배열, 모음 리스트 채우기
        alphabet[i] = c;
        if (c=='a'||c=='e'||c=='i'||c=='o'||c=='u') {
            vowelList.add(c);
        }
    }//for end

    //사전 순 정렬
    Arrays.sort(alphabet);

    isUsed = new boolean[alphabet.length];

    dfs(-1, 0, length, 0, 0);

    System.out.println(sb);
}//main() end

 

dfs()

public static void dfs(int index, int nowLen, int len, int con, int vowel) {
    if (nowLen==len
            && con>=2
            && vowel>=1) {
        sb.append(tempSb.toString()).append("\n");
        return;
    }

    //중복 허용 x (index+1부터 시작)
    for (int i = index+1; i < alphabet.length; i++) {
        if (!isUsed[i]) {
            //임시 sb에 현재 알파벳 기록
            tempSb.append(alphabet[i]);
            isUsed[i] = true;

            if (vowelList.contains(alphabet[i])) {
                //모음 추가
                dfs(i, nowLen+1, len, con, vowel+1);
            } else {
                //자음 추가
                dfs(i, nowLen+1, len, con+1, vowel);
            }

            //탐색 후 현재 알파벳을 임시 sb에서 지움
            tempSb.deleteCharAt(tempSb.length()-1);
            isUsed[i] = false;
        }
    }//for end
}//dfs() end