[백준] 12919 A와 B 2 - 완전탐색 (DFS) + 문자열 JAVA

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

12919번: A와 B 2

코드설명

DFS를 활용한 완전탐색 문제입니다.

 

처음에 시간초과가 났었습니다.

문제에 주어진대로, S에서 T로 가는 2가지 과정을 구현했으나, 

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

이러한 조건에서 S가 만약 1의 길이이고, T가 50의 길이라면, 최악의 경우 2^50 의 연산이 필요합니다.

 

그렇게하지않고, T -> S로 가능한지 확인해가면 시간초과가 일어나지않습니다.

로직은, 

- T의 맨 뒷자리가 'A' 일경우 'A'를 빼서 진행합니다.

- T의 REVERSE 한 맨 뒷자리가 'B'일경우 'B'를 빼서 진행합니다.

위의 방식을 통해 T->S로 찾아가면, 50번의 연산만 진행하면 됩니다.

 

Java 문법적으로 String과 StringBuilder에 대해 알아야할점은,

StringBuilder의 reverse 함수와 StringBuilder를 substring할시 String으로 변환되어 나온다는 것을 알아야합니다.

또한 String의 값을 비교하기 위해서는 equals를 사용해야합니다.

코드

시간초과

S -> T로 찾아가는 과정을 나타낸 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;



public class Main {
	
	public static int N;
	public static int[][] map;
	public static String S, T;
	public static int result = 0;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	S = st.nextToken();
    	st = new StringTokenizer(br.readLine());
    	T = st.nextToken();
    	
    	simulate(new StringBuilder(S), 0);
    	System.out.println(result);
    }
    
    public static void simulate(StringBuilder sb, int level) {
    	if(sb.length() > T.length()) {
    		return ;
    	}
    	
    	if(sb.toString().equals(T) ) {
    		result = 1;
    		return ;
    	}
    	
    	StringBuilder nsb = new StringBuilder(sb);
    	simulate(nsb.append('A'), level + 1);
    	nsb.deleteCharAt(nsb.length() - 1);
    	
    	simulate(new StringBuilder(sb.append('B').reverse()), level + 1);
    }
}

 

 

정답코드

T -> S 로 찾아가는 과정을 나타낸 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class Main {
	
	public static int N;
	public static int[][] map;
	public static String S, T;
	public static int result = 0;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	S = st.nextToken();
    	st = new StringTokenizer(br.readLine());
    	T = st.nextToken();
    	
    	simulate(S, T, T.length() - 1);
    	
    	
    	System.out.println(result);
    }
    public static void simulate(String s, String t, int lastIdx) {
    	
    	if(s.length() == t.length()) {
    		if(s.equals(t)) {
    			result = 1;
    		}
    		return ;
    	}
    	
    	//마지막숫자가 A인지 확인하고 맞다면 제거한뒤 진행
    	if(t.charAt(lastIdx) == 'A') {
    		simulate(s, t.substring(0, lastIdx), lastIdx-1);
    	}
    	
    	//문자열을 뒤집은 후에, 마지막 숫자가 B인지 확인하고 맞다면 제거한뒤 진행
    	StringBuilder sb = new StringBuilder(t).reverse();
    	if(sb.charAt(lastIdx) == 'B') {
    		simulate(s, sb.substring(0, lastIdx), lastIdx - 1);
    	}
    }
    
}