[백준] 12919 A와 B 2 - JAVA

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

12919번: A와 B 2

[12904 A와 B] 아주x10000 약간 업그레이드 문제 🫠

 

[풀이]

• A와 B (12904) 문제와 거의 비슷하다.
• 마찬가지로 S → T (x) , T → S 일때 가능한 경우의 수가 더 적다. 
• S에서 할 수 있는 방법은 A를 추가하거나, B를 추가하고 뒤집거나 두개 다 가능하다.
• 반대로 T에서 가능한 방법은, 각 조건에 따라 하나만 가능하거나 아예 안된다. 
  1. 가장 끝 단어가 'A' 일경우 : 가장 끝에 있는 A 빼기 
  2. 가장 "첫" 단어가 'B' 일경우 : 뒤집고 가장 "끝"에 있는 B 빼기
  ( 만약, 가장 첫단어가 'A'이고 끝단어가 'B'라면 (ex: ABB) 아무 것도 할 수 없다. 
• B를 추가 한 후에 뒤집는 것이기 때문에 반대로 T에서 탐색한다면 뒤집고 (가장 끝) B를 빼는 것이다. 

 

BFS 탐색을 통해, 하나의 문자열에 대해 가능한 경우의 문자열을 Queue에 넣어서 s와 같은 값이 되면 1 

---

 

[소스 코드]

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
        
		String s= br.readLine();
		String t= br.readLine();
		 
		System.out.println(bfs(s, t)); 
		
	}
	
	private static int bfs(String s, String t) {
		Queue<String> que= new LinkedList<>();
		que.add(t); 
		
		while(!que.isEmpty()) {
			String find = que.poll();

			if(find.equals(s)) return 1; 
			if(find.length() < s.length()) return 0; 
			
			//제일 마지막 글자가 a여야 지만 A를 뺄 수 있다. 
			if(find.charAt(find.length()-1) == 'A') 
				que.add(case1(find));
                
			if(find.charAt(0) == 'B')
				que.add(case2(find)); 
			
		}
		
		return 0; 
	}
	
	private static String case1(String s) {
		s = s.substring(0, s.length()-1); 
		return s; 
	}
	
	private static String case2(String s) {
		String rev = "";
		for(int i=s.length()-1; i>=0; i--) {
			rev += s.charAt(i); 
		}
		
		return rev.substring(0, rev.length()-1); 
	}
}//end of class