[백준] 2186 문자판 - DFS(깊이우선탐색) + DP(Dynamic Programming) JAVA

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

2186번: 문자판

코드설명

DFS(깊이우선탐색) + DP(Dynamic Programming) 를 활용하는 문제입니다.

 

문제에서 DFS를 활용해서 원하는 target 문자열을 찾는 부분은 쉽습니다.

이 문제에서 어려운점은 DP를 활용하는 방법입니다.

 

처음에는 DP를 단순하게 int[][][] dp 로 선언하고 안의 값들은 여전히 0 으로 둔채로 만약 0 이상의 값들일경우. 즉, 문자를 찾은경우에만 DP가 작동하도록 했습니다.

하지만, 위의 방식처럼 할경우 결국 어떠한 값도 존재하지 않을경우에는 모든 경우를 탐색합니다.

그렇기에, 처음에 DP[][][] 를 -1 로 모두 초기화 시킵니다.

두번째, DFS로 함수 시작시 해당 sR, sC, level을 방문했다는 의미로 DP[][][] = 0 으로 초기화 시킵니다.

이때 왜 Level을 굳이 활용하는가에 대한 궁금증이 생길 수 있는데, 같은 칸을 여러번 방문할 수 있기에 level을 선택해두어야 모든 경우를 다 확인할 수 있습니다. 만약 level이 없다면, 해당 칸에 한번 방문한다면 다시는 방문하지 못하겠습니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
	
	public static int N, M, K;
	public static int answer = 0;
	public static int[][] arr;
	public static int[][] map;
	public static int[] target;
	public static int[][][] dp;
	public static int[] dx = {-1,1,0,0};
	public static int[] dy = {0,0,-1,1};
	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());
    	
    	map = new int[N + 1][M + 1];
    	dp = new int[101][101][81];
    	for(int i=0; i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		String input = st.nextToken(); 
    		for(int j=0;j<M;j++) {
    			map[i][j] = input.charAt(j) - 'A';
    		}
    	}
    	
    	st = new StringTokenizer(br.readLine());
    	String targetS = st.nextToken();
    	target = new int[targetS.length()];
    	for(int i=0;i<targetS.length();i++) {
    		target[i] = targetS.charAt(i) - 'A';
    	}

//    	for(int i=0;i<N;i++) {
//    		for(int j=0;j<M;j++) {
//    			System.out.print(" "+map[i][j]);
//    		}
//    		System.out.println();
//    	}
//    	System.out.println();
//    	for(int i=0;i<targetS.length();i++) {
//    		System.out.print(target[i]+ " ");
//    	}
//    	System.out.println();
    	
    	for(int i=0;i<101;i++) {
    		for(int j=0;j<101;j++) {
    			Arrays.fill(dp[i][j], -1);
    		}
    	}
    	
    	for(int i=0;i<N;i++) {
    		for(int j=0;j<M;j++) {
    			if(map[i][j] == target[0]) {
    				answer += simulate(1, i, j);
    			}
    		}
    	}

    	System.out.println(answer);
    	
	}
	
	public static int simulate(int level, int sR, int sC) {
		if(dp[sR][sC][level] != -1) return dp[sR][sC][level];
		if(level == target.length) return 1; //만약 끝까지 온 경우라면 1개 추가합니다.
		
		dp[sR][sC][level] = 0;
		int cnt = 0;
		for(int dir = 0; dir < 4; dir++) {
			for(int move = 1; move <= K; move++) {
				int nr = sR + dx[dir] * move;
				int nc = sC + dy[dir] * move;
				if(nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
				
//				System.out.println(" "+target[level + 1] +" "+map[nr][nc]);
				if(target[level] == map[nr][nc] ) {
					cnt += simulate(level + 1, nr, nc);	
				}				
			}

		}
		return dp[sR][sC][level] = cnt;
	}
	
}