문제 풀이

S에서 T를 만들려고하면 DFS형식이든 BFS형식이든 불가능하다.
규칙을 이용해서 T를 S로 만들 수 있는지 확인하는 방식으로 푼다.

대부분 재귀로 풀었던데 나는 BFS로 풀었다.

맨 앞에 B가 있다면 이전에 규칙2를 적용해서 B를 추가하고 뒤집었다는 소리이므로
반대로 맨 앞을 없애고 뒤집어서 큐에 넣어준다.

맨 뒤에 A가 있다면 이전에 규칙1을 적용해서 A를 추가 했다는 소리이므로 A를 없애고 큐에 넣어준다.

만약에 큐에서 S와 같은 문자열이 나온다면 1을 출력하고 종료하면 된다.

문제 링크

boj/12919

소스코드

PS/12919.java

     import java.io.*;
    import java.util.*;


    public class Main {
        static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));


        public static void main(String[] args) throws IOException {
            String s = br.readLine();
            String t = br.readLine();
            Queue<String> q = new LinkedList<>();
            
            q.add(t);
            while (!q.isEmpty()) {
                String str = q.poll();
                if(str.equals(s))
                {
                    bw.write("1");
                    bw.flush();
                    return;
                }
                if(str.length() >= 2 &&str.charAt(0) == 'B')
                {
                    q.add(new StringBuilder(str.substring(1)).reverse().toString());
                }
                if(str.length() >= 2 && str.charAt(str.length() - 1) == 'A' )
                {
                    q.add(str.substring(0,str.length()-1));
                }
            }

            bw.write("0");
            bw.flush();

        }
    }