[PS] BOJ165000 문자열 판별 ( String ) with JAVA

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

16500번: 문자열 판별

 

 

◎문제 풀이

 

문자열 s가 주어질 때, 주어진 여러 개의 문자열 조합으로 s를 만들 수 있는지를 묻는 문제이다. 조합을 만드는 문제는 재귀호출로 풀면된다. 적절한 가지치기 조건을 두어 DFS 탐색을 하면 문제를 풀 수 있다. 

 

◎코드

import java.util.Scanner;

//BOJ165000 문자열 판별 ( 백트래킹 )
public class Main {

    public static String[] words;
    public static boolean[] visited;
    public static boolean flag;

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        String str = sc.next();
        int n = sc.nextInt();
        words = new String[n];
        visited = new boolean[n];

        for(int i=0;i<n;i++){
            words[i] = sc.next();
        }

        dfs("",str);

        if(flag) System.out.println(1);
        else System.out.println(0);

    }

    public static void dfs(String ans, String target){

        if(ans.equals(target)) {
            flag = true;
            return;
        }

        for(int i=0;i<words.length;i++){
            if(visited[i]) continue;

            String tmp = ans;
            String value = tmp+words[i];

            if(target.length() < value.length() ) continue; // 가지치기 조건1
            if(target.substring(0,value.length()).equals(value)){ // 가지치기 조건2
                visited[i] = true;
                dfs(value, target);
                visited[i] = false;
            }
        }
    }
}