[백준] 9177 단어 섞기 - 깊이우선탐색(DFS) + 동적계획법(DP) JAVA

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

 

코드설명

먼저 이 문제는 깊이우선탐색으로 풀 수 있습니다.

각 단어의 인덱스를 관리하면서 C가 마지막 길이까지 가면 성공한 것입니다.

 

처음에는 시간복잡도 고려하지 않고 접근했고, 시간초과가 발생했습니다.

시간복잡도는 최악의 경우 400^2 입니다.

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

public class Main {
    static int N;
    static String A, B, C;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());

        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            A = st.nextToken();
            B = st.nextToken();
            C = st.nextToken();
            
            System.out.println("Data set "+ (i+1)+": "+ ( solve(0, 0, 0) ? "yes" : "no") );
        }
        
    }

    static boolean solve(int a_idx, int b_idx, int c_idx){
    	if(c_idx == C.length()) {
    		return true;
    	}
    	
    	boolean ret = false;
        if(a_idx < A.length() && C.charAt(c_idx) == A.charAt(a_idx) ) {
        	ret |= solve(a_idx + 1, b_idx, c_idx + 1);
        }
        if(b_idx < B.length() && C.charAt(c_idx) == B.charAt(b_idx)) {
        	ret |= solve(a_idx, b_idx + 1, c_idx + 1);
        }
        
        return ret;
    }


}

 

이에 대해 동적계획법으로 대처했습니다.

package Main;

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

public class Main {
    static int N;
    static String A, B, C;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());

        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            A = st.nextToken();
            B = st.nextToken();
            C = st.nextToken();
            
            for(int j=0; j<205; j++) {
            	for(int k=0; k<205; k++) {
            		Arrays.fill(dp[j][k], -1);
            	}
            }
            System.out.println("Data set "+ (i+1)+": "+ ( solve(0, 0, 0) ? "yes" : "no") );
        }
        
    }
    
    static int[][][] dp = new int[205][205][410];
    static boolean solve(int a_idx, int b_idx, int c_idx){
    	if(dp[a_idx][b_idx][c_idx] == 1) return true;
    	else if(dp[a_idx][b_idx][c_idx] == 0) return false;
    	
    	if(c_idx == C.length()) {
    		return true;
    	}
    	
    	boolean ret = false;
        if(a_idx < A.length() && C.charAt(c_idx) == A.charAt(a_idx) ) {
        	ret |= solve(a_idx + 1, b_idx, c_idx + 1);
        }
        if(b_idx < B.length() && C.charAt(c_idx) == B.charAt(b_idx)) {
        	ret |= solve(a_idx, b_idx + 1, c_idx + 1);
        }
        
    	dp[a_idx][b_idx][c_idx] = ret ? 1 : 0;
        return ret;
    }


}

 

하지만, 좀 더 최적화시키면, 애초에 c_idx가 필요하지 않는걸 알 수 있습니다.

코드

c_idx는 a_idx + b_idx로 찾아냅니다.

좀 찜찜한점은, 목표 String이 전역적으로 선언되어있어 solve 함수내에서 참조되고 있기에 dp[A String][B String]으로만 충분한지 고민되지만, A, B, C의 변수값이 가변적이지 않기에 상관없습니다.

package Main;

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

public class Main {
    static int N;
    static String A, B, C;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());

        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            A = st.nextToken();
            B = st.nextToken();
            C = st.nextToken();
            
            for(int j=0; j<205; j++) {
        		Arrays.fill(dp[j], -1);
            }
            System.out.println("Data set "+ (i+1)+": "+ ( solve(0, 0) ? "yes" : "no") );
        }
        
    }
    
    static int[][] dp = new int[205][205];
//    현재 A의 앞 a_idx 글자, B의 앞 b_idx의 글자를 이미 사용했을떄 C의 앞글자를 만들 수 있는지를 반환하는 함수
    static boolean solve(int a_idx, int b_idx){
    	if(dp[a_idx][b_idx] == 1) return true;
    	else if(dp[a_idx][b_idx] == 0) return false;
    	
    	if((a_idx + b_idx) == C.length()) {
    		return true;
    	}
    	
    	boolean ret = false;
        if(a_idx < A.length() && C.charAt(a_idx + b_idx) == A.charAt(a_idx) ) {
        	ret |= solve(a_idx + 1, b_idx);
        }
        if(b_idx < B.length() && C.charAt(a_idx + b_idx) == B.charAt(b_idx)) {
        	ret |= solve(a_idx, b_idx + 1);
        }
        
    	dp[a_idx][b_idx] = ret ? 1 : 0;
        return ret;
    }


}