백준 2186. 문자판 :: 돼지개발자

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

"전형적인 DP 문제, 재귀 호출 및 리턴에 대해 잘 알고있자."

N,M 의 범위를 고려하면 100,000 개의 칸이 존재한다. 대략 계산해 봤을 때, 100*100 개 칸에서 갈 수 있는 방법의 개수는 4가지 방향에 최대 5칸의 거리 20개가 된다. 20^100,000 ... 브루트 포스로는 절대 돌아가지 않는다. 100 * 100 격자에 모든 문자가 'B' 이며 'BB' 를 만드는 경우의 수를 생각해보면 굉장히 많다. 그리디한 방법도 없고, 이럴 때는 DP 를 이용해 푸는 것이 좋겠다. 

사실 이런 격자 문제를 풀때 DP를 사용하면 나는 항상 DP[X][Y][?]  이런 식으로 놓고 생각해본다. 무엇을 어떻게 메모이제이션 할 것인가를 생각해야 할 듯 하다. 해당 문제에서는 현재 위치에서 탐색한 가능한 경로의 수를 저정하기로 했고, 아래와 같이 dp를 만들기로 했다.

dp[X][Y][찾고자하는 문자열의 INDEX] = 가능한 경우의수

아래 기저사례나 dp를 이용해 가지치기하는 도중에 dp 값을 넣는 과정 없이 그냥 return 을 시켜버려서 시간이 오래 걸렸었다. 해당 부분을 아래와 같이 수정했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
 
    static int N,M,K;
    static char[][] map;
    static int[][][] dp;
    static int res;
    static int[] dx = {0,0,1,-1};
    static int[] dy = {1,-1,0,0};
    static char[] str;
    static int length;
    
    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 char[N][M];
        
        for (int i = 0; i < N; i++) {
            map[i] = br.readLine().toCharArray();
        }
        
        str = br.readLine().toCharArray();
        length = str.length;
        
        dp = new int[N][M][length];
        
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                Arrays.fill(dp[i][j], -1);
            }
        }
        
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                res += solve(i,j,0);
            }
        }
        System.out.println(res);
    }
 
    static int solve(int x, int y, int idx ) {
        
        if(idx == length - 1 ) return dp[x][y][idx] = 1;
        if(dp[x][y][idx] != -1) return dp[x][y][idx];
        if(map[x][y] != str[idx]) return dp[x][y][idx] = 0;
        
        dp[x][y][idx] = 0;
        
        for (int i = 0; i < 4; i++) {
            for (int k = 1; k <= K; k++) {
                int nx = x + dx[i] * k;
                int ny = y + dy[i] * k;
                
                if(!isRange(nx, ny) || map[nx][ny] != str[idx+1])
                    continue;
                
                dp[x][y][idx] += solve(nx,ny,idx+1);    
            }
        }
        return dp[x][y][idx];
    }
    
    static boolean isRange(int x, int y) {
        if(x < 0 || x >= N || y < 0 || y >= M)  return false;
        return true;
    }
}