[백준][1759번 : 암호만들기]

문제

문제링크

바로 어제 최백준 조교가 방 열쇠를 주머니에 넣은 채 깜빡하고 서울로 가 버리는 황당한 상황에 직면한 조교들은, 702호에 새로운 보안 시스템을 설치하기로 하였다. 이 보안 시스템은 열쇠가 아닌 암호로 동작하게 되어 있는 시스템이다.
암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다. 또한 정렬된 문자열을 선호하는 조교들의 성향으로 미루어 보아 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되었을 것이라고 추측된다. 즉, abc는 가능성이 있는 암호이지만 bac는 그렇지 않다.
새 보안 시스템에서 조교들이 암호로 사용했을 법한 문자의 종류는 C가지가 있다고 한다. 이 알파벳을 입수한 민식, 영식 형제는 조교들의 방에 침투하기 위해 암호를 추측해 보려고 한다. C개의 문자들이 모두 주어졌을 때, 가능성 있는 암호들을 모두 구하는 프로그램을 작성하시오.

코드

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class Main {

    static int L,C;
    static char[] data;
    static List<String> result;

    public static void main(String[] args)throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] str = br.readLine().split(" ");
        L = Integer.parseInt(str[0]);
        C = Integer.parseInt(str[1]);

        data = new char[C];
        result = new LinkedList<>();

        String[] str2 = br.readLine().split(" ");
        for(int i=0; i<C; i++){
            data[i] = str2[i].charAt(0);
        }

        //데이터 정렬
        Arrays.sort(data);
        dfs(0,0,0,-1,"");
        for(String s : result){
            System.out.println(s);
        }

    }
    static void dfs(int length, int ja, int mo, int curIndex, String pwd){ // 길이,자음,모음,현재자리,암호
        // 1. 체크인 - 생략 가능
        // 2. 목적지인가? - 길이 + 자음,모음 개수
        if(length == L){ // 길이가 L일 때
            if(ja >= 2 && mo >=1){
                result.add(pwd);
            }
        } else{
            // 3. 연결된 곳을 순회 - 나보다 높은 알파벳
            for (int nextIndex = curIndex + 1; nextIndex < data.length; nextIndex++) {
                char nextData = data[nextIndex];
                //      4. 갈 수 있는가? - 생략 가능
                if(nextData =='a' || nextData =='e' || nextData =='i' || nextData =='o' || nextData =='u'){
                //      5. 간다. - dfs(next) - 자음, 모음
                    dfs(length+1, ja, mo+1, nextIndex, pwd+nextData);
                }else{
                //      5. 간다. - dfs(next) - 자음, 모음
                    dfs(length+1, ja+1, mo, nextIndex, pwd+nextData);
                }
                
            }
        }
        // 6. 체크아웃 - 생략 가능
    }
}

※ 코드 설명

Arrays.sort(data) 시작할 때 정렬하는 이유는 문제 조건으로
(abc는 가능성이 있는 암호이지만 bac는 그렇지 않다.) 라고 했기 때문에 정렬을 하게된다면 불필요한 탐색을 줄일 수 있다.

dfs(0,0,0,-1,"")에서 curIndex를 -1 준 이유는

for (int nextIndex=curIndex+1; nextIndex<data.length; nextIndex++)

위 코드는 dfs안에 있는 반복문때문이다. 여기서 암호를 만들기 위해 다음 문자를 확인하기 위해서 현재 index에서 +1 를 해주기 때문에 시작 인덱스 0으로 시작하기 위해서는 -1를 줘야한다.

if(nextData =='a' || nextData =='e' || nextData =='i' || nextData =='o' || nextData =='u'){
	dfs(length+1, ja, mo+1, nextIndex, pwd+nextData);
}else{
	dfs(length+1, ja+1, mo, nextIndex, pwd+nextData);
}

자음과 모음을 비교해서 자음일 때는 자음 +1를 하고 모음일 때는 모음 +1를 하여 dfs 함수를 호출한다.(재귀)