2023.03.06 ~ 2023.03.10 스터디

이번 주 스터디에서 백트래킹 알고리즘 문제를 함께 풀었습니다.

📌 암호 만들기

암호 만들기 문제는 L개의 알파벳 소문자로 구성된 암호를 만들려고 하는데, 이때 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있어야합니다. 또한 알파벳이 증가하는 순서로 배열되어 있어야합니다.

C개의 알파벳 소문자가 주어졌을 때, 가능성이 있는 암호들을 모두 출력하는 문제입니다.

예를 들어, 아래와 같이 입력이 주어졌다고 가정하겠습니다.

4 6
a t c i s w

그러면 가능성이 있는 암호들은 아래와 같습니다.

acis
acit
aciw
acst
acsw
actw
aist
aisw
aitw
astw
cist
cisw
citw
istw

알파벳이 증가하는 순서로 출력된 것을 확인할 수 있습니다.

💡 코드

public class Main {
    private static int l, c;
    private static char[] ch, temp;
    private static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 만들어야 될 암호 문자 개수와 주어지는 알파벳 개수 입력
        StringTokenizer st = new StringTokenizer(br.readLine());
        l = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());

        ch = new char[c];
        temp = new char[l];

        // 알파벳 입력
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<c; i++)
            ch[i] = st.nextToken().charAt(0);

        // 오름차순 정렬
        Arrays.sort(ch);

        backtracking(0 , 0);

        bw.write(sb.toString());
        bw.flush();

        bw.close();
        br.close();
    }

    public static void backtracking(int depth, int start){
        // 만들어야 될 문자의 개수가 완성됐다면
        if(depth==l){
            // 그 문자의 모음과 자음 개수 확인
            if(check()) {
                for (char c : temp) {
                    sb.append(c);
                }
                sb.append('\n');
            }
            return;
        }

        for(int i=start; i<c; i++){
            temp[depth] = ch[i];
            backtracking(depth+1, i+1);
        }
    }

    // 모음, 자음 개수 확인
    public static boolean check() {
        int vow = 0, con = 0; // 모음, 자음 개수

        for(int i=0; i<temp.length; i++){
            char c = temp[i];

            if(c=='a' || c=='e' || c=='i' || c=='o' || c=='u')
                vow++;
            else
                con++;
        }

        if(vow>=1 && con>=2)
            return true;

        return false;
    }
}

백준에서 N과 M 시리즈의 문제를 풀었다면 큰 틀의 코드를 구현할 수 있을 것입니다.

• backtracking() 메서드에서 for 문 안에는 임시 배열인 temp에 입력으로 주어진 오름차순으로 정렬된 암호 문자들을 하나 씩 넣어주면서 함수를 재귀호출하여 암호 문자를 생성합니다. 이때, for 문 안에 i 값은 backtracking() 메서드에서 인자로 넣어주는 값으로 하여 입력으로 주어진 문자를 다시 처음부터 temp배열에 넣어주지 않게합니다.

• 이런 식으로 재귀호출하혀 암호 문자가 L개로 구성된다면 문제에서 요구한 대로 암호 문자의 모음과 자음 개수를 확인해야 합니다.

• 그래서 check() 메서드에는 암호 문자를 하나 씩 확인하여 모음과 자음 개수를 계산하여 모음 1개 이상, 그리고 자음 2개 이상이면 true를 반환하도록 합니다.

---

📌 뮤탈리스크

뮤탈리스크 문제는 스타크래프트에서 나오는 저그 유닛입니다.

그래서 이 문제를 요약하자면 뮤탈리스크 1개 남았고, SCV가 N개 남은 상태에서 뮤탈리스크가 한 번 공격하는데 3개의 SCV를 공격할 수 있습니다.

그때, 첫 번째로 공격받은 SCV는 체력 9를 잃고, 두 번째는 3, 세 번째는 1의 체력을 잃습니다.

SCV의 체력이 0 또는 그 이하가 되면 SCV는 파괴됩니다.

모든 SCV를 파괴하기 위해 공격해야 하는 횟수의 최솟값을 출력하는 문제입니다.

예를 들어, 아래와 같이 SCV의 개수와 체력이 주어졌을 때,

3
12 10 4

1, 3, 2 순서대로 공격을 하면, 남은 체력은 (12-9, 10-1, 4-3) = (3, 9, 1)이 남고, 2, 1, 3 순서대로 공격을 하면, 남은 체력은 (0, 0, 0)이기 때문에 공격 최솟값은 다음과 같습니다.

2

💡 코드

public class Main {
    // 뮤탈리스크의 공격 패턴
    private static int[][] pattern = {  {-9, -3, -1},{-9, -1, -3},
                                        {-3, -9, -1},{-3, -1, -9},
                                        {-1, -3, -9},{-1, -9, -3}   };
    // scv의 최대 체력
    private static int[][][] dp = new int[61][61][61];
    private static int answer = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // scv의 수
        int n = Integer.parseInt(br.readLine());

        int[] arr = new int[3];

        // scv의 체력 입력
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        solve(arr, 0);

        bw.write(answer+"");
        bw.flush();

        bw.close();
        br.close();
    }

    public static void solve(int[] arr, int count) {
        // 각 scv 체력 저장
        int a1 = arr[0];
        int a2 = arr[1];
        int a3 = arr[2];

        // 최솟값보다 현재 공격 횟수가 같거나 클 경우 종료
        if(answer <= count) return;

        // 이미 방문한 곳이고 현재 공격 횟수(count)보다 더 작을 경우 종료
        if(dp[a1][a2][a3] != 0 && dp[a1][a2][a3] <= count) return;

        // 현재 공격 횟수로 방문 표시
        dp[a1][a2][a3] = count;

        // scv가 모두 파괴되었다면 최솟값 갱신
        if(a1==0 && a2==0 && a3==0){
            answer = Math.min(answer, count);
            return;
        }
        // 뮤탈리스크의 6가지 공격 패턴을 적용하여 탐색
        for(int i=0; i<6; i++){
            int scv1 = Math.max(a1+pattern[i][0], 0);
            int scv2 = Math.max(a2+pattern[i][1], 0);
            int scv3 = Math.max(a3+pattern[i][2], 0);

            solve(new int[]{scv1, scv2, scv3}, count+1);
        }
    }
}

• DFS와 DP를 이용하여 해결합니다.

• 뮤탈리스크의 6가지 공격 패턴을 미리 2차원 배열에 저장합니다.

• DP에는 3차원 배열로 각 SCV의 남은 체력 인덱스에 현재 공격 횟수를 저장합니다. 이는 그래프에서 방문을 표시하는 visited 변수와 비슷한 역할을 합니다.

• for 문을 통해 뮤탈리스크의 6가지 공격 패턴을 적용하여 count+1과 함께 solve() 메서드를 재귀호출합니다.

• 이런 식으로 재귀호출 하면서 각 SCV의 남은 체력이 0이 되어버리면 최솟값을 갱신하고 return합니다.

• 만약, 계속 재귀호출하다가 갱신된 최솟값보다 현재 공격 횟수가 같거나 더 크다면 더 진행할 필요가 없으므로 return합니다.

• 마찬가지로, 계속 재귀호출하다가 dp를 이용하여 이미 방문했고 dp에 저장된 공격 횟수보다 현재 공격 횟수가 같거나 더 크다면 더 진행할 필요가 없으므로 return합니다.