백준 12919번 A와 B 2 (JAVA)

https://www.acmicpc.net/problem/12919

12919번: A와 B 2

 

저는 해당 문제를 BFS를 이용해 문제를 해결하였습니다.

문제 그대로 s문자열부터 시작해서 두가지 명령을 하면서 t와 같은지를 BFS하게 되면 시간 초과가 나오게 됩니다.

그래서 저는 역으로 t부터 시작해 s와 같은지를 BFS를 하였습니다.

역으로 하게 되면 맨 앞글자가 'B'일때는 두번째 연산, 마지막 글자가 'A'일때는 첫번째 연산의 역을 하면 되기 때문에 

정순으로 했을 때보다 더 적게 탐색하게 될 것입니다. 

 

 

package BOJ.etc;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

public class BOJ_12919 {
    private static final int SUCCESS = 1;
    private static final int FAIL = 0;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        String t = br.readLine();
        System.out.println(bfs(s,t));
    }
    public static int bfs(String s,String t){
        Queue<String> q = new LinkedList<>();
        Set<String> visited  = new HashSet<>();
        q.offer(t);
        while(!q.isEmpty()){
            String now = q.poll();
            if(now.equals(s)){
                return SUCCESS;
            }
            if(now.length() <= s.length()){
                continue;
            }
            if(now.charAt(0) == 'B'){
                StringBuilder sb = new StringBuilder(now);
                sb.deleteCharAt(0);
                sb = sb.reverse();
                String next = sb.toString();
                addQueue(next,visited,q);
            }
            if(now.charAt(now.length()-1) == 'A'){
                String next = now.substring(0,now.length()-1);
                addQueue(next,visited,q);
            }
        }
        return FAIL;
    }
    private static void addQueue(String next, Set<String> visited,Queue<String> q){
        if(!visited.contains(next)){
            visited.add(next);
            q.offer(next);
        }
    }
}