[PS] BOJ12919 A와B 2 ( String, DFS ) with JAVA

12919번: A와 B 2

 

◎ 문제풀이

 

문제를 보고 DFS 알고리즘을 잘 떠올렸으나 시간초과가 발생하였다. 

 

 

 

Source를 Target으로 만들기 위해 DFS로 모든 경우를 탐색하였다. 문제를 풀면서도 시간초과를 예상하기는 했다. 

 

 

 

Source 끝에 A를 추가하거나 

Source 끝에 B를 추가하거 뒤집어야 한다.

 

Source와 Target의 길이 차이만큼 경우의 수는 2ⁿ 으로 늘어난다.

Target의 최대길이가 50이므로 경우의 수는 2의 49승까지 늘어날 수 있다. 

위 그림을 보면 BAA가 중복되는 것을 확인할 수 있다.

 

그러므로 백트래킹 조건을 넣지 않으면

시간초과가 날 수 밖에 없다.

그러나 나는 마땅한 백트래킹 조건을 찾지 못했다. 

 

답을 찾아보니 Source에서 Target이 아니라 Target에서 Source를 맞추면 되었다.

역으로 Target에서 Source를 맞출 생각을 안한 것은 아니지만 구현력이 부족했던 것 같다. 

 

Target : BAABA 이면  두 가지 경우를 예상할 수 있다.

 

 

BAABA의 이전 문자열은 두 가지 경우 중 하나이다. 

 

1) BAAB 

2) ABAA

 

BAAB에 A를 추가하면 BAABA가 되고

ABAA에 B를 추가하고 뒤집으면 BAABA가 된다. 

 

이후 탐색에서 백트래킹이 된다.

 

BAAB는  끝이 A가 아니므로 앞이 B인 경우만 생각하면 된다.

ABAA는 앞이 B가 아니므로 뒤가 A인 경우만 생각하면 된다. 

 

 

 

 

위에서 처럼 기하급수적으로 경우의 수가 증가하지 않는다. 

탐색할 가치가 있는 것만 선택되어 탐색이 이루어진다. 

 

그럼 이를 코드로 구현해보자. 

 

 

◎ 코드

 

시간초과가 발생한 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

//BOJ12919 A 와 B 2 ( 시간 초과 발생 )
public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        String t = br.readLine();

        boolean flag = dfs(t,s);

        if(flag) System.out.println(1);
        else System.out.println(0);

    }

    public static boolean dfs(String t , String curr){

        if(t.length() == curr.length()){
            return t.equals(curr);
        }

        // 1. A 추가 하기
        if(dfs(t,curr+"A")) return true;

        // 2. B 추가하고 문자열 뒤집기
        StringBuffer sb = new StringBuffer(curr+"B");
        if(dfs(t,sb.reverse().toString())) return true;

        return false;

    }
}

 

 

정답인 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

//BOJ12919 A 와 B 2
public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        String t = br.readLine();

        if(dfs(t,s)) System.out.println(1);
        else System.out.println(0);

    }

    public static boolean dfs(String curr , String target){

        if(curr.length() == target.length()){
            return curr.equals(target);
        }

        // 앞이 B인 경우, B를 제가하고 뒤집기
        if(curr.charAt(0) == 'B'){
            StringBuilder sb = new StringBuilder(curr.substring(1,curr.length()));
            if(dfs(sb.reverse().toString(),target)) return true;
        }
        
        // 뒤가 A인 경우, A를 제거하기
        if(curr.charAt(curr.length()-1) == 'A'){
            if(dfs(curr.substring(0,curr.length()-1),target)) return true;
        }

        return false;

    }
}