[백준] 12919 A와 B 2 (자바 풀이)

문제

수빈이는 A와 B로만 이루어진 영어 단어 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다.

이런 사실에 놀란 수빈이는 간단한 게임을 만들기로 했다. 두 문자열 S와 T가 주어졌을 때, S를 T로 바꾸는 게임이다. 문자열을 바꿀 때는 다음과 같은 두 가지 연산만 가능하다.

• 문자열의 뒤에 A를 추가한다.
• 문자열의 뒤에 B를 추가하고 문자열을 뒤집는다.

주어진 조건을 이용해서 S를 T로 만들 수 있는지 없는지 알아내는 프로그램을 작성하시오. 

 

문제풀이

import java.util.*;

public class Main {
    static String target;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        target = in.next();
        String S = in.next();
        boolean flag = dfs(S);

        if (flag == true) {
            System.out.print(1);
        } else {
            System.out.print(0);
        }
    }

    public static boolean dfs(String str) {
        if (str.length() == target.length()) {
            if (str.equals(target)) return true;
            return false;
        }

        if (str.charAt(str.length() - 1) == 'A') {
            if (dfs(str.substring(0, str.length() - 1))) {
                return true;
            }
        }
        
        if (str.charAt(0) == 'B') {
            StringBuilder sb = new StringBuilder(str);
            if (dfs(sb.reverse().substring(0, str.length() - 1))) {
                return true;
            }
        }
        return false;
    }
}

 

문제에서는 아래 두가지의 작업을 통해서 S -> T(목표 단어) 를 만들 수 있는지 확인한다.

문자열 뒤에 A를 추가한다.

문자열 뒤에 B를 추가하고 뒤집는다.

 

조건의 반대로 적용해 T -> S를 만들 수 있는지 확인한다. 

문자열 맨 뒤가 A라면 A를 제거하고

문자열 시작이 B라면 뒤집고 B를 제거하는 과정을 거쳐서 답을 구하였다.