백준 12919번 A와B 2(JAVA)

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

12919번: A와 B 2

 

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

하지만 문제의 내용을 그대로 코드로 짜게 된다면 시간 초과가 나오게 될 것입니다.

그래서 저는 문제를 반대로 생각하였습니다.

T(긴 문자열)에서 S(짧은 문자열)로 만들수 있는지를 BFS로 코드를 작성하였습니다.

S에서 T로 BFS코드를 작성하는 경우, 추가하는 조건만 있기 때문에 점점 많은 문자열들이 BFS queue에 들어가게 될 것입니다.

반대의 경우, 첫번째 'A'를 문자열에 추가한다는 맨 뒤에 'A'인지 확인하고 제거하고 Queue에 넣고 , 두번째 조건은 문자열이 'B'를 첫번째 문자로 가지고 있는지 확인하고 Queue에 넣게 되어 가지치기하기 때문에 처음보다 적은 문자열을 Queue에 넣게 될 것입니다.

 

package BOJ.Bruteforce;

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 {

    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));
    }
    private static int bfs(String start,String target){
        Queue<String> q = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        visited.add(target);
        q.offer(target);
        while(!q.isEmpty()){
            String now = q.poll();
            if(now.length() == start.length() && now.equals(start)){
                return 1;
            }
            if(now.length() <= start.length()){
                continue;
            }
            if(now.charAt(now.length()-1) == 'A'){
                String temp = new StringBuilder(now).deleteCharAt(now.length() - 1).toString();
                if(!visited.contains(temp)){
                    visited.add(temp);
                    q.offer(temp);
                }
            }
            if(now.charAt(0) == 'B'){
                String temp = new StringBuilder(now).reverse().deleteCharAt(now.length() - 1).toString();
                if(!visited.contains(temp)){
                    visited.add(temp);
                    q.offer(temp);
                }
            }
        }
        return 0;
    }
}