[백준_12919번] A와 B 2

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의 길이)

 

[코드]

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

public class BaekJoon_12919 {
	static String s,t;
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		s=br.readLine();
		t=br.readLine();
		
		if(DFS(s,t))
			System.out.println(1);
		else
			System.out.println(0);
	}
	
	// 문자열 T를 다시 문자열 S로 만들 수 있는가를 확인해야 시간초과 나지 않음
	static boolean DFS(String s, String t) {
		if(s.length()==t.length()) {
			if(s.equals(t))
				return true;
			else
				return false;
		}
		
		// 맨 끝자리가 A인 경우 -> 맨 뒤에 A를 빼는 것으로 연산 역행
		if(t.charAt(t.length()-1)=='A') { 
			if(DFS(s,t.substring(0,t.length()-1)))
				return true;
		}
		
		// 맨 앞자리가 B인 경우 -> 맨 앞의 B를 제거하고, 문자열을 뒤집어 연산 역행
		if(t.charAt(0)=='B') {
			StringBuilder sb=new StringBuilder();
			sb.append(t.substring(1,t.length()));
			if(DFS(s,sb.reverse().toString()))
				return true;
		}
		return false;
	}
}

 

[고찰]

 처음 이번 문제의 해결방법으로 떠올랐던 것은 문자열 S를 T로 만드는 것이었다. 큐를 사용하여 수행할 수 있는 연산 2가지를 통해 나온 결과물을 다시 큐에 삽입하는 BFD 알고리즘으로 코드를 짰지만 메모리초과를 받았다. 

 이번 문제의 핵심은 '문자열 T에 2가지 연산을 역수행 하여 문자열 S를 만들수 있는가' 이다. 맨 뒤에 문자 A를 추가하는 연산은 T의 맨 끝자리가 A인 경우에 A를 삭제하는 것으로 역수행 할 수 있고, 맨 뒤에 문자 B를 추가하고 문자열을 뒤집는 연산은 T의 맨 앞자리가 B인 경우에 B를 삭제하고 문자열을 뒤집는 것으로 역수행 할 수 있다. DFS 알고리즘을 사용하여 두 가지 연산을 구현하면 시간초과 없이 정답처리를 받을 수 있었다.

 이번 문제를 풀면서 시간초과나 메모리초과를 받는 경우 다른 방식으로 문제를 접근하는 시각을 길러야한다는 것을 더 느꼈다.