문제

풀이과정

그리디 문제
완전 탐색을 기반으로 하지만, 기존의 탐색 방법과는 다르게 접근해야한다.
시작부터 목표 언어까지 접근하게 되는 경우, 찾는 데 꽤 많은 메모리와 시간을 소모하여, 틀렸다는 답이 나오게 되더라.
그렇기 때문에, 시작과 목표점을 서로 바꾸어, 목표점에서 시작하여 변화시키는 과정 중에 똑같은 문자가 나오는지 확인하면 문제를 보다 효율적으로 풀 수 있다.
완전 탐색의 경우, BFS 를 적용하였다.

아마 이게 top-down, bottom-up 의 차이 인듯 한데, 요 원리가 그리디에 속하는지는 잘 모르겠다.

정답

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

public class Main {
    static String strS;
    static String strT;

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

        solution(strT);

        System.out.println(0);
    }

    private static void solution(String st) {
        Queue<String> q = new LinkedList<>();
        q.add(st);

        while (!q.isEmpty()) {
            String curr = q.poll();
            if (curr.equals("")) continue;

            if (curr.equals(strS)) {
                System.out.println(1);
                System.exit(0);
            }

            if (curr.charAt(curr.length() - 1) == 'A') {
                q.add(curr.substring(0, curr.length() - 1));
            } else {
                StringBuilder sb = new StringBuilder();
                for (int i = curr.length()-2; i >= 0; i--) {
                    sb.append(curr.charAt(i));
                }
                q.add(sb.toString());
            }
        }
    }
}