14238번 - 출근기록(dp, dfs)

문제:

A는 매일 매일 출근할 수 있다. B는 출근한 다음날은 반드시 쉬어야 한다. C는 출근한 다음날과 다다음날을 반드시 쉬어야 한다. 따라서, 모든 출근 기록이 올바른 것은 아니다. 예를 들어, B는 출근한 다음날 쉬어야 하기 때문에, "BB"는 절대로 나올 수 없는 출근 기록이다. 

출근 기록 S가 주어졌을 때, S의 모든 순열 중에서 올바른 출근 기록인 것 아무거나 출력하는 프로그램을 작성하시오.

첫째 줄에 출근 기록 S가 주어진다. S의 길이는 50을 넘지 않는다.

S의 모든 순열 중에서 올바른 출근 기록인 것을 하나만 출력한다. 만약, 올바른 출근 기록이 없는 경우에는 -1을 출력한다.

 

풀이:

올바른 출근기록 하나만 출력해야 하며, 각 출근 기록의 길이는 동일하다.

즉, 올바른 순열이며, 출근 기록의 길이와 순열의 길이가 같으면, 해당 순열을 출력하면 되는 문제이다.

bfs로 풀면 모든 순열을 다 검사해야 하지만,

dfs로 접근하면, 운이 좋으면 한번에, 운이 나빠도 bfs와 큰 차이없이 정답에 도달할 수 있다.

 

하지만 dfs라도, 중복을 방지할 수는 있을 것이다.

위에서 주어진 조건에 따르면, B는 뒤의 한칸, C는 뒤의 두칸까지 영향을 미친다.

즉, 사용한 A, B, C의 수와 두칸 뒤까지 문자열이 중복된다면, 이전까지 어떻게 문자를 배치했던 간에 중복에 해당된다.

ex) CBAACB, ACBACB 

 

뒤의 두칸까지 고려해야 하는 이유는 아래 두 예시를 보면 이해될 것이다.

ex) CBAABC, CBAACB

CBAABC 뒤에는 B가 나올 수 있지만, CBAACB 뒤에는 B가 나올 수 없다.

ex)CBAACA, CBACAA

둘다 A 3개, B 1개, C 2개가 사용된 문자열이지만, CBAACA 뒤에는 C가 나올 수 없다.

 

위의 설명을 토대로 고려해야하는 조건을 나열해보자.

1. 출근 기록의 길이와 만들어진 문자열의 길이가 같으면 해당 문자열을 반환한다.
2. 사용한 A, B, C의 수와 두칸 뒤까지 문자열이 중복되는지 확인한다.
3. 두칸 뒤에 어떤 문자가 있는지 살펴본다.
   1. C가 있다.
      1. 한칸 뒤에 B가 있다면
         1. 남은 A가 있다면 문자열에 A를 추가한다.
      2. 한칸 뒤에 A가 있다면
         1. 남은 A가 있다면 문자열에 A를 추가한다.
         2. 남은 B가 있다면 문자열에 B를 추가한다.
   2. C이외의 문자(A, B)가 있다.
      1. 한칸 뒤에 C가 있다면
         1. 남은 A가 있다면 문자열에 A를 추가한다.
         2. 남은 B가 있다면 문자열에 B를 추가한다.
      2. 한칸 뒤에 B가 있다면
         1. 남은 A가 있다면 문자열에 A를 추가한다.
         2. 남은 C가 있다면 문자열에 C를 추가한다.
      3. 한칸 뒤에 A가 있다면
         1. 남은 A가 있다면 문자열에 A를 추가한다.
         2. 남은 B가 있다면 문자열에 B를 추가한다.
         3. 남은 C가 있다면 문자열에 C를 추가한다.

위 조건을 토대로 메서드를 작성해보았다.

static void dfs(int back, int backBack, int A, int B, int C, boolean[][][][][] dp, String S) {
    if (A + B + C == 0) { // 모든 문자를 다 사용했다면
        System.out.println(S);
        System.exit(0);
    }

    // 중복체크
    if (dp[back][backBack][A][B][C]) {
        return;
    }
    dp[back][backBack][A][B][C] = true;

    if (backBack == 3) { // 두칸 뒤에 C가 있을 때
        if (back == 2) { // 한칸 뒤에 B가 있을 때
            if (A > 0) {
                dfs(1, back, A-1, B, C, dp, S + "A");
            }
        } else { // 한칸 뒤에 A가 있을 때
            if (A > 0) {
                dfs(1, back, A-1, B, C, dp, S + "A");
            }
            if (B > 0) {
                dfs(2, back, A, B-1, C, dp, S + "B");
            }
        }
    } else { // 두칸 뒤에 C가 있지 않다면
        if (back == 3) { // 한칸 뒤에 C가 있을 때
            if (A > 0) {
                dfs(1, back, A-1, B, C, dp, S + "A");
            }
            if (B > 0) {
                dfs(2, back, A, B-1, C, dp, S + "B");
            }
        } else if (back == 2){ // 한칸 뒤에 B가 있을 때
            if (A > 0) {
                dfs(1, back, A-1, B, C, dp, S + "A");
            }
            if (C > 0) {
                dfs(3, back, A, B, C-1, dp, S + "C");
            }
        } else { // 한칸 뒤에 A또는 아무것도 없을 때
            if (A > 0) {
                dfs(1, back, A-1, B, C, dp, S + "A");
            }
            if (B > 0) {
                dfs(2, back, A, B-1, C, dp, S + "B");
            }
            if (C > 0) {
                dfs(3, back, A, B, C-1, dp, S + "C");
            }
        }
    }
}

좀 조건문이 많은 메서드가 나왔다.

A는 1, B는 2, C는 3, 빈칸은 0으로 구분해서 조건문을 수행한다.

 

전체코드:

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String S = sc.nextLine();
        int len = S.length();

        int A = 0;
        int B = 0;
        int C = 0;

        for (int i = 0; i < len; i++) { // A, B, C 수 체크
            if (S.charAt(i) == 'A') {
                A++;
            } else if (S.charAt(i) == 'B') {
                B++;
            } else {
                C++;
            }
        }

        // dp[한칸 뒤 문자][두칸 뒤 문자][남은 A][남은 B][남은 C]
        boolean[][][][][] dp = new boolean[4][4][A+1][B+1][C+1];

        dfs(0, 0, A, B, C, dp, "");
        System.out.println(-1);

    }

    static void dfs(int back, int backBack, int A, int B, int C, boolean[][][][][] dp, String S) {
        if (A + B + C == 0) { // 모든 문자를 다 사용했다면
            System.out.println(S);
            System.exit(0);
        }

        // 중복체크
        if (dp[back][backBack][A][B][C]) {
            return;
        }
        dp[back][backBack][A][B][C] = true;

        if (backBack == 3) { // 두칸 뒤에 C가 있을 때
            if (back == 2) { // 한칸 뒤에 B가 있을 때
                if (A > 0) {
                    dfs(1, back, A-1, B, C, dp, S + "A");
                }
            } else { // 한칸 뒤에 A가 있을 때
                if (A > 0) {
                    dfs(1, back, A-1, B, C, dp, S + "A");
                }
                if (B > 0) {
                    dfs(2, back, A, B-1, C, dp, S + "B");
                }
            }
        } else { // 두칸 뒤에 C가 있지 않다면
            if (back == 3) { // 한칸 뒤에 C가 있을 때
                if (A > 0) {
                    dfs(1, back, A-1, B, C, dp, S + "A");
                }
                if (B > 0) {
                    dfs(2, back, A, B-1, C, dp, S + "B");
                }
            } else if (back == 2){ // 한칸 뒤에 B가 있을 때
                if (A > 0) {
                    dfs(1, back, A-1, B, C, dp, S + "A");
                }
                if (C > 0) {
                    dfs(3, back, A, B, C-1, dp, S + "C");
                }
            } else { // 한칸 뒤에 A또는 아무것도 없을 때
                if (A > 0) {
                    dfs(1, back, A-1, B, C, dp, S + "A");
                }
                if (B > 0) {
                    dfs(2, back, A, B-1, C, dp, S + "B");
                }
                if (C > 0) {
                    dfs(3, back, A, B, C-1, dp, S + "C");
                }
            }
        }
    }
}

 

시행착오:

처음에는 dfs만 생각하고, dp를 이용할 생각을 하지 못했다.

그 결과 시간초과가 되었고, 그 코드는 아래와 같다.

bCount와 cCount라는 변수를 이용했으나, 별로 효과적이지 못하다.

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String S = sc.nextLine();

        int A = 0;
        int B = 0;
        int C = 0;

        for (int i = 0; i < S.length(); i++) {
            if (S.charAt(i) == 'A') {
                A++;
            } else if (S.charAt(i) == 'B') {
                B++;
            } else {
                C++;
            }
        }

        dfs(A, B, C, "", S.length(), 0, 0);

        System.out.println(-1);

    }

    static void dfs(int A, int B, int C, String S, int count, int bCount, int cCount) {
        if (count == 0) {
            System.out.println(S);
            System.exit(0);
        }

        if (bCount == 0 && cCount == 0) {
            if (A > 0) {
                dfs(A - 1, B, C, S + "A", count - 1, 0, 0);
            }
            if (B > 0) {
                dfs(A, B - 1, C, S + "B", count - 1, 1, cCount);
            }
            if (C > 0) {
                dfs(A, B, C, S + "C", count - 1, 0, 2);
            }
        } else if (bCount > 0 && cCount > 0) {
            if (A > 0) {
                dfs(A - 1, B, C, S + "A", count - 1, 0, 0);
            }
        } else if (bCount > 0) {
            if (A > 0) {
                dfs(A - 1, B, C, S + "A", count - 1, 0, 0);
            }
            if (C > 0) {
                dfs(A, B, C, S + "C", count - 1, 0, 2);
            }
        } else if (cCount > 0) {
            if (A > 0) {
                dfs(A - 1, B, C, S + "A", count - 1, 0, cCount-1);
            }
            if (B > 0) {
                dfs(A, B - 1, C, S + "B", count - 1, 1, cCount-1);
            }
        }

    }
}

이후, 중복을 줄이기 위해 Set 자료구조를 이용했으나, 메모리초과로 실패하였다. 

 

결국 해당 블로그를 참고하게 되었고, prev와 prevprev 변수 이용 방식을 참고하였다.

[JAVA] 백준 14238번 출근 기록 (tistory.com)

[JAVA] 백준 14238번 출근 기록

 

너무 많은 조건문 탓에 풀고 나서도 의심이 가던 문제이다.

조건문이 많으면, 그만큼 시간이 오래걸려서 좋아하지 않는다.

하지만 각 조건문이 반드시 필요한 조건문이었다.

여러 조건을 dp를 이용하여 검사하는 방식에 대해 배울 수 있었다.

가끔은 조건문에 조금은 관대해져도 괜찮을 듯 하다.