백준(BOJ) 2186 : 문자판 (JAVA)

문제링크 : https://www.acmicpc.net/problem/2186

2186번: 문자판

DFS로 풀면 되는 문제다. 단순 DFS로 풀었을 때의 시간복잡도는... 아... 어떻게 계산해야할까-_- (필자가 나중에 시간이 되면 계산에 도전해보도록 하겠다;;;) 하여간 어마어마(?)할 것이다. 한 번의 탐색에서 같은 칸을 방문할 수 없다고 한다고 해도 시간복잡도가 어마어마할텐데(이 경우에는 백트래킹으로 풀 것이다), 심지어 같은 칸을 여러 번 방문할 수 있다고 한다. 단순 DFS로 풀면 안 된다; 뭔가 대책이 필요하다. 바로 메모이제이션이다. 코드는 아래와 같다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
    private static int[] di = {-1, 1, 0, 0};
    private static int[] dj = {0, 0, -1, 1};
    private static int n;
    private static int m;
    private static int k;
    private static int trgtLen;
    private static int[][][] dp;
    
    public static void main(String[] args) throws Exception {
        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());
        
        char[][] board = new char[n][m];
        
        for(int i = 0; i < n; i++) {
            board[i] = br.readLine().toCharArray();
        }
        
        char[] goal = br.readLine().toCharArray();
        trgtLen = goal.length;
        dp = new int[n][m][trgtLen];
        
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                Arrays.fill(dp[i][j], -1);
            }
        }
        
        int cnt = 0;
        
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {                
                if(board[i][j] == goal[0]) {
                    cnt += dfs(board, goal, i, j, 0);
                }
            }
        }
        
        System.out.println(cnt);
    }
 
    private static int dfs(char[][] board, char[] goal, int i, int j, int depth) {
        
        if(dp[i][j][depth] != -1) {
            return dp[i][j][depth];
        }
        
        if(depth == trgtLen - 1) {
            return 1;
        }
        
        int cnt = 0;
        
        for(int a = 1; a <= k; a++) {
            for(int b = 0; b < 4; b++) {
                int nextI = i + di[b] * a;
                int nextJ = j + dj[b] * a;
                
                if(nextI >= 0 && nextJ >= 0 && nextI < n && nextJ < m && board[nextI][nextJ] == goal[depth + 1]) {
                    cnt += dfs(board, goal, nextI, nextJ, depth + 1);
                }
            }
        }
        
        return dp[i][j][depth] = cnt;
    }
}

 

여기서 dp[i][j][x]가 가리키는 값은, 문자판의 (i, j)의 위치를 depth=x 인 경우에 방문했을 때 나올 수 있는 경로의 수이다.

 

위 그림을 통해 좀 더 설명해보겠다. BREAK를 탐색하는 문제라고 가정했을 때 처음 윗쪽 B에서 탐색을 시작한다. 그리고 빨간색 E를 주목하자. E에서는 각각 좌우로 A, K로 가면 답이 나온다. 즉 이 위치에서 정답으로 갈 수 있는 경우의 수는 2개이다. 그리고 이번엔 밑쪽 B에서 탐색을 시작해보자. E에 도착했을 때, 굳이 A, K로 또 탐색을 할 필요가 있을까? 이미 여기에서 정답이 나오는 경우의 수가 2개라는 걸 알지 않는가? 이 정도 설명으로 이해가 됐으리라고 본다. '메모이제이션을 할 때 depth까진 저장할 필요가 없지 않나?'란 생각을 할 수도 있다. 근데 만들어야하는 영단어가 'AABAAA'와 같은, 같은 알파벳이 중복된 것일 수도 있기 때문에 depth에 따른 경우의 수를 저장해야한다.