[백준] 12904번 : A와 B

12904번: A와 B

---

[문자열 + BFS]

이 문제는 정공법으로 풀면 안된다. s -> t를 가는게 아닌, t -> s를 가는 것을 생각해야 한다. 전자로 풀면 메모리 초과가 날 수 있다. 따라서 t -> s로 가는 방법으로 풀어보자.

 

1. 문자열의 끝이 'A'이면 맨 끝 문자 삭제

2. 문자열의 끝이 'B'이면 맨 끝 문자 삭제 후 뒤집기

 

나는 Set을 이용해 방문을 표시했엇으나, 굳이 필요하지 않음을 느꼈다. 따라서 반복문의 종료 조건은 문자열의 길이가 s와 같고, 문자열이 s와 동일할 때 종료하도록 설정했다.

# Code </>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main {

    static String s, t;

    static boolean BFS(){

        int length = s.length();
        boolean possible = false;
        Queue<String> Q = new LinkedList<>();

        Q.add(t);

        while(!Q.isEmpty()){
            String cur = Q.poll();
            int curLen = cur.length();

            if(cur.length() < length) break;
            if(cur.length() == length && cur.equals(s)) return true;

            StringBuilder sb = new StringBuilder(cur);

            if(cur.charAt(curLen - 1) == 'A')
                sb.deleteCharAt(curLen-1);

            else if(cur.charAt(curLen - 1) == 'B'){
                sb.deleteCharAt(curLen-1);
                sb.reverse();
            }

            Q.add(sb.toString());
        }
        return possible;
    }

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

        s = br.readLine();
        t = br.readLine();

        System.out.println(BFS()? 1:0);
    }
}