[백준 / 골드5] 12919 A와 B 2 (Java)

문제 보기

사용한 것

• 같아질때까지 탐색하기 위한 DFS

풀이 방법

• DFS를 문자 하나씩 빼주면서 돌린다.
  • 문자를 하나씩 더해주면 시간 초과
  • 빼주면서 계산하면 "A"를 맨뒤에 더한 경우, "B"를 맨뒤에 더하고 뒤집은 경우가 진행됐을 때만 체크하여 탐색할 수 있다.
• cur과 target의 길이가 같아지면 같은 문자열이면 1을, 다른 문자열이면 0을 return
• ret가 0보다 크면 1을, 0이면 0을 return

코드

public class Main {

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

        System.out.println(dfs(b, a));
    }

    static int dfs(String cur, String target) {
        if (cur.length() == target.length()) {
            if (cur.equals(target)) {
                return 1;
            }

            return 0;
        }

        int ret = 0;
        if(cur.charAt(0) == 'B') {
            ret += dfs(new StringBuilder(cur.substring(1)).reverse().toString(), target);
        }
        if(cur.charAt(cur.length() - 1) == 'A'){
            ret += dfs(cur.substring(0, cur.length() - 1), target);
        }
        return ret > 0 ? 1 : 0;
    }
}