문자판 [백준 2186][골드3][Java]

 

[광고 누르면 오늘의 행운 상승!!]

 

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

2186번: 문자판

DP 문제인걸 알고 풀어도 풀기 힘들다 ..

1. DP에 알맞는 값을 채워 넣는다 ( -1: 방문하지 않았다. , 0 : 방문했는데 유망하지 않았다. , 1: 유망하다)

2. DFS에 진입할 때마다 DP의 값을 확인해서 이미 계산이 끝난 곳이면 방문하지 않는다.

3. 끝까지 도달했을때 문자가 일치한다면 1을 반환한다. 

4. 맵을 전부 돌면서 가능한 경로를 더한다.

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

public class 문자판 {
	public static final int[] dx = {-1,0,1,0};
	public static final int[] dy = {0,1,0,-1};
	public static char map[][];
	public static int N,M,K,L;
	public static char[] S;
	public static int[][][] dp;
	
	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("test.txt"));
		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());
		
		map = new char[N][M];
		
		
		for (int i = 0; i < N; i++) {
			map[i] = br.readLine().toCharArray();
		}
		
		S = br.readLine().toCharArray();
		L = S.length;
		dp  = new int[N][M][L];
		
		for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                Arrays.fill(dp[i][j], -1);
            }
        }
		int ans = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				ans += dfs(i,j,0);
			}
		}
		System.out.println(ans);
		
	}
	public static int dfs(int row, int col, int cnt) {
		//마지막 문자열까지 정답이다
		if(cnt == L-1) {
			dp[row][col][cnt] = 1;
			return 1;
		}
		//방문한 곳이라면 저장했던 DP를활용한다.
		if(dp[row][col][cnt] != -1) return dp[row][col][cnt];
		//문자가 맞지 않으면 0으로 채운다.
		if(map[row][col] != S[cnt]) {
			dp[row][col][cnt] = 0;
			return 0;
		}
		
		dp[row][col][cnt] = 0;
		
		 for (int i = 0; i < 4; i++) {
	            for (int k = 1; k <= K; k++) {
	                int nx = row + dx[i] * k;
	                int ny = col + dy[i] * k;
	                
	                //맵을 벗어나거나 다음 문자가 정답 문자열과 다른 경우
	                if(!check(nx, ny) ||map[nx][ny] != S[cnt+1] )continue;
	               
	                //다음위치가 유망할 경우
	                dp[row][col][cnt] += dfs(nx,ny,cnt+1);    
	            }
	        }
	        return dp[row][col][cnt];
	    }
	    
	    static boolean check(int x, int y) {
	        if(x < 0 || x >= N || y < 0 || y >= M)  return false;
	        return true;
	    }

}