#백준_2186 문자판 - Java

# 유형 : 탐색

# 분류에 bfs라고 적혀있어서, bfs로 풀었는데 시간 초과 / dfs로 접근하였으나 범위가 너무 넓어 시간초과 /  질문검색을 통해 dp로 메모라이징하면서 dfs탐색을 하라고해서 구현하였음. 문제를 풀기 전 잘 모르겠다면 dp+dfs에 대해 한번 알아보고 풀어보길 권장함.

 

package bj;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class p2186 {
    
    static int cnt=0;
    static int N,M,K;
    static char arr[][];
    static int dp[][][];
    static boolean visit[][];
    static String target;
    static int moveX[] = {0,1,0,-1};
    static int moveY[] = {-1,0,1,0};
    
    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());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        
        arr = new char[N][M];
        
        for(int i=0; i<N; i++) {
            String str = br.readLine();
            for(int j=0; j<M; j++) {
                arr[i][j] = str.charAt(j);
            }
        }
        target = br.readLine();
        dp = new int[N][M][target.length()];
        
        for(int i=0; i<N; i++) {
            for(int j=0; j<M; j++) {
                for(int k=0; k<target.length(); k++) {
                    dp[i][j][k] = -1;
                }
            }
        }
        
        for(int i=0; i<N; i++) {
            for(int j=0; j<M; j++) {
                cnt+=dfs(i,j,0);
            }
        }
        
        
        
        System.out.println(cnt);
        
    }
    
    public static int dfs(int i, int j, int index) {
        if(index == target.length()-1)
            return dp[i][j][index] = 1;
        if(dp[i][j][index] != -1)
            return dp[i][j][index];
        if(arr[i][j] != target.charAt(index))
            return dp[i][j][index] = 0;
        
        dp[i][j][index] = 0;
        
        for(int d=0; d<4; d++) {
            for(int k=1; k<=K; k++) {
                int newX = j + moveX[d]*k;
                int newY = i + moveY[d]*k;
                
                if(0<=newY && newY<N && 0<=newX && newX<M && arr[newY][newX]==target.charAt(index+1)) {
                    dp[i][j][index] += dfs(newY,newX,index+1);
                }
            }
        }
        
        return dp[i][j][index];
    }
}