[Java] BaekJoon 14238. 출근 기록 (골드3) (DFS) (DP)

문제 출처: https://www.acmicpc.net/problem/14238

14238번: 출근 기록

문제 이해

 

목표

강호(A): 매일
준규(B): 다음날은 어야함
수빈(C): 다음날과 다다음날을 쉬어야함
주어진 출근 기록 S중 올바른 출근기록인것 아무거나 출력

 

 

풀이

1. 길이가 최대 50이 될 수 있는 S
2. S의 순서를 바꿀 수 있는 순열을 구한다. 
  -> 가능한 순열이 있다면 출력한다. 
  -> 모든 순열을 조사해도 없으면 -1을 출력한다. 

 

3. 순열을 만들 때 
 -> 매 자릿수에 값을 채울 때마다 A, B, C의 개수를 카운트해서 넣어준다. 넣어줄 때마다 -1 (dfs) 
 -> 재귀가 끝나는경우 
     - 조건을 모두 만족해서 자릿수를 다 채워서 한번이라도 올바른 출근 배열이 나오면 
       -> check = true로 처리하고 리턴
     - 재귀의 case를 줄이기 위해, visited[countA][countB][countC][pre][pre]를 배열로 만들어 visited 처리를 해야한다.
       => 방문했던 방법에 다시 재귀하지 않기 위해

 

소스코드

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

public class 출근기록 {
    private static char[] answer;
    private static int N;
    private static boolean check;
    private static boolean[][][][][] visited; // A-0 B-1 C-2

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String S = br.readLine();
        N = S.length();
        check = false;
        visited = new boolean[50][50][50][3][3];
        int countA = 0;
        int countB = 0;
        int countC = 0;
        for (int i = 0; i < N; i++) {
            if (S.charAt(i) == 'A') {
                countA++;
            } else if (S.charAt(i) == 'B') {
                countB++;
            } else {
                countC++;
            }
        }
        getPermutation(new char[N], 0, countA, countB, countC, 0, 0);
        StringBuilder sb = new StringBuilder();
        if(check){
            for (char c : answer) {
                sb.append(c);
            }
        } else {
            sb.append(-1);
        }
        System.out.println(sb);

    }

    private static void getPermutation(char[] chars, int depth, int countA, int countB, int countC, int pre, int pre2) {
        if(check || visited[countA][countB][countC][pre][pre2]){
            return;
        }

        if (countA == 0 && countB == 0 && countC == 0) {
            check = true;
            answer = chars;
            return;
        }

        visited[countA][countB][countC][pre][pre2] = true;

        if (countC >= 1 && !check && pre != 2 && pre2 != 2) {
            chars[depth] = 'C';
            getPermutation(chars, depth + 1, countA, countB, countC - 1, 2 ,pre);
        }
        if (countB >= 1 && !check && pre != 1) {
            chars[depth] = 'B';
            getPermutation(chars, depth + 1, countA, countB - 1, countC, 1, pre);
        }
        if (countA >= 1 && !check) {
            chars[depth] = 'A';
            getPermutation(chars, depth + 1, countA - 1, countB, countC, 0, pre);
        }

    }
}

 

 

초기 잘못된 코드

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

public class Main {
    private static char[] answer;
    private static int N;
    private static boolean check;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String S = br.readLine();
        N = S.length();
        check = false;
        int countA = 0;
        int countB = 0;
        int countC = 0;
        for (int i = 0; i < N; i++) {
            if (S.charAt(i) == 'A') {
                countA++;
            } else if (S.charAt(i) == 'B') {
                countB++;
            } else {
                countC++;
            }
        }

        getPermutation(new char[N], 0, countA, countB, countC);
        StringBuilder sb = new StringBuilder();
        if(check){
            for (char c : answer) {
                sb.append(c);
            }
        } else {
            sb.append(-1);
        }
        System.out.println(sb);

    }

    private static void getPermutation(char[] chars, int depth, int countA, int countB, int countC) {
        if(check){
            return;
        }

        if (depth == N) {
            check = true;
            answer = chars;
            return;
        }

        if (countC >= 1 && !check &&
                (depth == 0 ||
                depth == 1 && chars[depth - 1] != 'C' ||
                (depth >= 2 && chars[depth - 1] != 'C' && chars[depth - 2] != 'C'))) {
            chars[depth] = 'C';
            getPermutation(chars, depth + 1, countA, countB, countC - 1);
        }

        if (countB >= 1 && !check &&
                (depth == 0 ||
                depth >= 1 && chars[depth - 1] != 'B')) {
            chars[depth] = 'B';
            getPermutation(chars, depth + 1, countA, countB - 1, countC);
        }

        if (countA >= 1 && !check) {
            chars[depth] = 'A';
            getPermutation(chars, depth + 1, countA - 1, countB, countC);
        }

    }
}

출력결과는 일치 !! -> 시간초과 !!

 

초기 코드는

- pre와 pre2를 통해 이전 값들을 매개변수로 더 편하게 관리할 수 있는 상황을 고려하지 않았다.

- 재귀의 case를 줄이기 위해, visited[countA][countB][countC][pre][pre]를 배열로 만들어 visited 처리를 하지 않았다.

 => 아이디어 제공(출처): https://velog.io/@pss407/%EB%B0%B1%EC%A4%8014238-%EC%B6%9C%EA%B7%BC-%EA%B8%B0%EB%A1%9D

 

 

확인

 

만약 확인해야하는 값이 적다면 매개변수로 활용할 수 있음을 알자 !!

 

dfs에서 같은 case를 최소한으로 탐색하기 위해서 dp를 활용해 가지치기 하는 법을 알아야겠다 !!