[BOJ 12904] A와 B (Java)

nnm·2020년 2월 17일
0

BOJ 12904 A와 B

문제풀이

주어진 상태로부터 특정한 연산을 통해 목표 상태로 도달하는 문제에서 반대로 생각하여 목표 상태에서 역연산을 통해 시작 상태로 도달하게 한다면 경우의 수를 많이 줄일 수 있다. 이 문제 또한 반대로 생각하는 아이디어가 가장 중요한 문제였다.

구현코드

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

public class Main {
	
	static Queue<StringBuilder> q;
	static String S, T;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		S = br.readLine();
		T = br.readLine();
		
		q = new LinkedList<>();
		StringBuilder sb = new StringBuilder(T);
		
		if(bfs(sb)) System.out.println(1);
		else System.out.println(0);
	}

	private static boolean bfs(StringBuilder sb) {
		q.offer(sb);
		
		while(!q.isEmpty()) {
			StringBuilder now = q.poll();
			
			if(now.toString().equals(S)) {
				return true;
			}
			
			// 목표 문자열의 길이보다 커야한다.
			if(now.length() > S.length()) {
				StringBuilder next = null;
				// 뒤에서 A를 제거하기 
				if(now.charAt(now.length() - 1) == 'A') {
					next = new StringBuilder(now.substring(0, now.length() - 1));
					q.offer(next);
				}
				
				// 뒤에서 B를 제거하고 뒤집기
				if(now.charAt(now.length() - 1) == 'B') {
					next = new StringBuilder(now.subSequence(0, now.length() - 1));
					next.reverse();
					q.offer(next);
				}
			}
		}
		return false;
	}

}
profile
그냥 개발자

0개의 댓글