[백준] 12919 A와 B 2 - Java

 

 

 

문제 출저

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

12919번: A와 B 2

 

 

 

문제 풀이

BFS를 통해 풀었습니다. 

시작 문자열 s, 목표 문자열 t가 주어집니다. 

s에서 시작해 t로 도달 할 수 있는지 구해야 합니다. 2가지 동작을 하 수 있습니다. 뒤에 A를 붙이거나 뒤에 B를 붙이고 두집을 수 있습니다. 

 

처음 문제를 풀 때 s부터 시작해 t로 탐색을 진행했습니다. 이 때, 시간 복잡도 초과가 발생했습니다. 

탐색의 순서를 바꾸어 t에서 s로 가도록 바꿨습니다. 

t에서 마지막 문자가 A면 A를 뺍니다.

t에서 처음 문자가 B면 B를 빼고 순서를 뒤집습니다.

조건에 따라 탐색을 수행하기 때문에 시간 복잡도가 줄어들어 해결할 수 있었습니다. 

 

 

소스 코드

package baekjoon.year24.month4.day2130.day24;

import javax.sound.sampled.Line;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

/*
A와 B 2
https://www.acmicpc.net/problem/12919

11% 시간초과
A,B 를 1, 0으로 바꾸는 방법

s에서 t로 가는게 아니라
t에서 s로 간다.

앞에 B가 있다면 B를 뺀 다음 뒤집는다.
뒤에 A가 있다면 A를 뺀다.

 */

public class B12919 {

    static String s;
    static String t;
    static Set<String> visited;

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

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

        Queue<String> que = new LinkedList<>();
        que.add(t);
        while (!que.isEmpty()) {
            String temp = que.poll();

            if (temp.charAt(temp.length()-1) == 'A') {
                String s1 = temp.substring(0, temp.length() - 1);

                if (s1.equals(s)) {
                    System.out.println(1);
                    return;
                }

                if (s1.length() < s.length()) continue;

                que.add(s1);
            }

            if (temp.charAt(0) == 'B') {
                String temp2 = temp.substring(1, temp.length());
                StringBuilder sb = new StringBuilder();
                for (int i = temp2.length()-1; i >= 0; i--) {
                    sb.append(temp2.charAt(i));
                }
                String s2 = sb.toString();

                if (s2.equals(s)) {
                    System.out.println(1);
                    return;
                }

                if (s2.length() < s.length()) continue;

                que.add(s2);
            }

        }

        System.out.println(0);

    }

}