[백준 12919번] A와 B 2 - java

한번 틀려서 다시 풀었었다.

문제 설명

1. S 랑 T가 주어진다.
2. S 뒤에 'A' 를 붙이거나, S 뒤에 'B'를 붙이고 뒤집을 수 있다.
3. 2번의 연산을 통해서 S랑 T가 같아지면 1, 그렇게 못만들면 0을 출력하면 된다.

잘못된 풀이 과정

1. BF + DFS문제이다.
2. S에서 위의 연산을 하나씩 수행해간다.
    - A를 붙여줌
    - B를 붙이고 뒤집음
3. 그리고 길이가 T랑 같아졌을 때 비교해서 처리한다.
    - (틀린 이유) 시간초과가 발생했는데 모든 경우에서 시간복잡도가 2^N이 되기 때문이다.
6. S로부터 시작해서 T가 될 때까지 2번씩 N번 수행된 것.

코드

import java.util.*;

public class Main
{
    private static String T;
    private static int ans = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String S = sc.next();
        T = sc.next();

        StringBuilder before = new StringBuilder();
        before.append(S);

        DFS(before, 'A');
        DFS(before, 'B');

        System.out.println(ans);
    }

    private static void DFS(StringBuilder before, char adder) {
        if (ans == 1) return;
        StringBuilder now = new StringBuilder(before);

        if (adder == 'A') {
            now.append(adder);
        } else {
            now.append(adder);
            now.reverse();
        }

        if (now.length() == T.length()) {
            if (now.toString().equals(T)) {
                ans = 1;
            }
            return;
        }

        DFS(now, 'A');
        DFS(now, 'B');
    }
}

 

다른 방법으로 풀었는데

 

정답 풀이 과정

1. BF + DFS문제이다.
2. S에서부터가 아니라 반대로 T에서 부터 S가 될 때까지 수행해 준다.
 3.  앞의 로직에서 약간의 가지치기를 더한다.
 4.  결국은 A를 더해주거나 B를 더한 후에 뒤집는건데, 이 경우를 체크해서 그 때만 로직을 해주면 된다. (여기 해당하지 않으면 계산 안함)      - A로 끝나면 빼주고 DFS
    - B로 시작하면 돌려서 뺴주기
5. 이렇게 해주면 더이상 처리해주지 않아도 되는 케이스는 무시할 수 있다.
    - 근데 사실 이것도 worst case는 2^N이기는 할듯?

 

import java.util.*;

public class Main
{
    private static String S;
    private static int ans = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        S = sc.next();
        String T = sc.next();

        StringBuilder before = new StringBuilder();
        before.append(T);

        DFS(before);
        System.out.println(ans);
    }

    private static void DFS(StringBuilder before) {
        if (ans == 1) return;

        if (before.length() == S.length()) {
            if (before.toString().equals(S)) {
                ans = 1;
            }
            return;
        }

        if (before.toString().endsWith("A")) {
            StringBuilder now = new StringBuilder(before);
            now.deleteCharAt(now.length() - 1);
            DFS(now);
        }

        if (before.toString().startsWith("B")) {
            StringBuilder now = new StringBuilder(before);
            now.reverse();
            now.deleteCharAt(now.length() - 1);
            DFS(now);
        }

    }
}