[백준] Gold V. 암호만들기

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

 

사용 알고리즘

 

• DFS
• 백트래킹

 

풀이

 

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

public class Main {
    static int l, c;
    static char [] arr;
    static boolean [] visited;
    static List<String> res = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        l = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());

        String [] input = br.readLine().split(" ");
        arr = new char[c];
        visited = new boolean[c];


        for(int i = 0; i < input.length; i++){
            arr[i] = input[i].charAt(0);
        }
        Arrays.sort(arr);
        dfs(0, 0, "");
        for (String re : res) {
            System.out.println(re);
        }
    }

    public static void dfs(int start, int depth, String tmp) {
        if (depth == l && check(tmp)) {
            res.add(tmp);
            return;
        }


        for(int i = start; i < c; i++) {
            if (!visited[i]) {
                visited[i] = true;
                dfs(i + 1, depth + 1, tmp + arr[i]);
                visited[i] = false;
            }
        }
    }

    public static boolean check(String tmp) {
        int mc = 0;
        int jc = 0;
        for (char c : tmp.toCharArray()) {
            if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
                mc++;
            }
            else {
                jc++;
            }
        }
        if (mc >= 1 && jc >= 2) return true;
        return false;
    }
}import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int l, c;
    static char [] arr;
    static boolean [] visited;
    static List<String> res = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        l = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());

        String [] input = br.readLine().split(" ");
        arr = new char[c];
        visited = new boolean[c];


        for(int i = 0; i < input.length; i++){
            arr[i] = input[i].charAt(0);
        }
        Arrays.sort(arr);
        dfs(0, 0, "");
        for (String re : res) {
            System.out.println(re);
        }
    }

    public static void dfs(int start, int depth, String tmp) {
        if (depth == l && check(tmp)) {
            res.add(tmp);
            return;
        }


        for(int i = start; i < c; i++) {
            if (!visited[i]) {
                visited[i] = true;
                dfs(i + 1, depth + 1, tmp + arr[i]);
                visited[i] = false;
            }
        }
    }

    public static boolean check(String tmp) {
        int mc = 0;
        int jc = 0;
        for (char c : tmp.toCharArray()) {
            if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
                mc++;
            }
            else {
                jc++;
            }
        }
        if (mc >= 1 && jc >= 2) return true;
        return false;
    }
}

 

 

회고

 

처음에 백트래킹으로 푸려고 생각은 했는데 어떤식으로 접근해야 할 지 막혀서 고민이 많았다. 답지를 보고 싶은 욕구가 샘솟았으나 지금까지 풀었던 수많은 백트래킹 문제를 생각하니 무조건 혼자 풀어야겠다고 다짐했다.

 

일단 맨 처음에, 만들 수 있는 모든 경우의 수를 출력해 보았다. 그러다보니, 재귀 종료 조건에 depth 조건 뿐만 아니라, 한개 이상의 모음, 두개 이상의 모음을 체크하는 조건이 있어야 한다고 생각해서 따로 메서드를 빼주었다.

 

하지만, 초기 코드에선 시작점(start)를 설정하지 않았어서 모든 경우의 수를 출력해주었다! 그래서 시작점을 매번 업데이트 시켜주니 정상적으로 원하는 값만 출력이 됐다.

 

마지막으로 정렬을 해야 했는데, 입력값을 처음에 배열에 저장할 때 sort 해주면 자연스럽게 사전 순으로 순회를 한다.

 

 

번외

입력값을 받는 부분인데,

4 6
a t c i s w

 

 

char [] 형태의 배열에 a t c i s w를 넣어줘야 하는데 공백때문에 살짝의 변형이 필요하다.

 

이렇게 공백 단위로 잘라서 String 형태의 배열에 저장하거나

String [] input = br.readLine().split(" ");
for(int i = 0; i < input.length; i++){
    arr[i] = input[i].charAt(0);
}

 

StringTokenizer로 바로 넣어주는 방법도 있다.

st = new StringTokenizer(br.readLine());
for(int i = 0; i < c; i++){
    arr[i] = st.nextToken().charAt(0);
}

 

 

여기서 살짝 시간이 뺏겼어서 짚고 넘어가고 싶었다.