[백준]12919: A와 B 2(java)

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

12919번: A와 B 2

문제

수빈이는 A와 B로만 이루어진 영어 단어 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다.

이런 사실에 놀란 수빈이는 간단한 게임을 만들기로 했다. 두 문자열 S와 T가 주어졌을 때, S를 T로 바꾸는 게임이다. 문자열을 바꿀 때는 다음과 같은 두 가지 연산만 가능하다.

• 문자열의 뒤에 A를 추가한다.
• 문자열의 뒤에 B를 추가하고 문자열을 뒤집는다.

주어진 조건을 이용해서 S를 T로 만들 수 있는지 없는지 알아내는 프로그램을 작성하시오. 

입력

첫째 줄에 S가 둘째 줄에 T가 주어진다. (1 ≤ S의 길이 ≤ 49, 2 ≤ T의 길이 ≤ 50, S의 길이 < T의 길이)

출력

S를 T로 바꿀 수 있으면 1을 없으면 0을 출력한다.

예제 입력 1 

A
BABA

예제 출력 1 

1

---

처음 bottom-up방식으로 접근을했는데 경우의수가 너무 많아져 시간초과가 발생했다.

그래서 Top-Down 방식으로 바꿔서 접근해보았다.

 

BABA는

두가지경우로 내려갈 수 있다.

BAB에서 +A를 한경우

 

ABA에 B를 붙이고 뒤집은 경우

두가지이다.

BABA > ABA 여기서 우리는 첫글자가 B라면 제거하고 뒤집음으로서 역행할 수 있음을 알 수 있다.

 

bfs와 dfs 풀이 두가지를 모두 공유하겠다.

 

bfs 전체 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class BJ_G4_1504_특정한최단경로 {
    static class Node implements Comparable<Node>{
        int end;
        int cost;

        Node(int end, int cost) {
            this.end = end;
            this.cost = cost;
        }

        @Override
        public int compareTo(Node o) {
            return this.cost - o.cost;
        }
    }
    static ArrayList<Node>[] list;
    static int N, E;
    static final int INF = 200000000;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] dist1, distV1, distV2;
        N = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());

        list = new ArrayList[N+1];
        dist1 = new int[N+1];
        distV1 = new int[N+1];
        distV2 = new int[N+1];

        for(int i=1; i<=N; i++) {
            list[i] = new ArrayList<>();
            dist1[i] = INF;
            distV1[i] = INF;
            distV2[i] = INF;
        }

        for(int i=0; i<E; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            list[a].add(new Node(b, c));
            list[b].add(new Node(a, c));
        }
        st = new StringTokenizer(br.readLine());

        int v1 = Integer.parseInt(st.nextToken());
        int v2 = Integer.parseInt(st.nextToken());

        dijkstra(1, dist1);
        dijkstra(v1, distV1);
        dijkstra(v2, distV2);

        // 1 > v1 > v2 > N
        int sum1 =  dist1[v1] + distV1[v2] + distV2[N];
        // 1 > v2 > v1 > N
        int sum2 =   dist1[v2] + distV2[v1] + distV1[N];
        int ans = Math.min(sum1, sum2);

        if(ans >= INF) {
            System.out.println(-1);
        } else {
            System.out.println(ans);
        }
    }
    private static void dijkstra(int start, int[] dist) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(start, 0));
        dist[start] = 0;

        while(!pq.isEmpty()) {
            Node now = pq.poll();

            if(now.cost > dist[now.end]) {
                continue;
            }

            int len = list[now.end].size();

            for(int i=0; i<len; i++) {
                Node next = list[now.end].get(i);

                if(dist[next.end] <= now.cost + next.cost) continue;
                dist[next.end] = now.cost + next.cost;
                pq.add(new Node(next.end, now.cost+next.cost));
            }
        }

    }
}

dfs 전체 코드

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

public class Main {

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

        String str = br.readLine();
        String ans = br.readLine();

        dfs(ans, str);
        System.out.println(0);
    }

    // 스택
    /*

     */

    public static void dfs(String nowStr, String ans) {
        if(nowStr.length() == ans.length()) {
            if(nowStr.equals(ans)) {
                System.out.println(1);
                System.exit(0);
            }
            return;
        }

        if(nowStr.charAt(nowStr.length() - 1) == 'A') {
            dfs(nowStr.substring(0, nowStr.length()-1), ans);
        }
        if(nowStr.charAt(0) == 'B') {
            StringBuilder str = new StringBuilder(nowStr.substring(1, nowStr.length()));
            dfs(str.reverse().toString(), ans);
        }
    }
}