[백준] 2186 문자판 java

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

public class CharBoard {
    static BufferedReader br;
    static StringTokenizer st;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static char[] ansWord;
    static char[][] board;
    static int[][][] dp;
    static int n, m, k;
    static int ans;

    public static void main(String[] args) throws IOException{
        input();
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(board[i][j] == ansWord[0]) ans += dfs(0, i, j);
            }
        }
        System.out.println(ans);
    }

    static void input() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        ans = 0;
        board = new char[n][m];
        for(int i = 0; i < n; i++) {
            board[i] = br.readLine().toCharArray();
        }
        ansWord = br.readLine().toCharArray();
        dp = new int[n][m][ansWord.length];
        for(int[][] a : dp) {
            for(int[] b : a) {
                Arrays.fill(b, -1);
            }
        }
    }

    static int dfs(int idx, int x, int y) {
        //마지막 문자까지 왔다는건 그 전까지 계속 유망했으며 주어진 단어와 동일하다는 뜻이므로 1 반환
        if(idx == ansWord.length-1) return dp[x][y][idx] = 1;
        //현재 위치가 이미 방문한적 있는 위치일 경우 메모이제이션 된 값 리턴
        if(dp[x][y][idx] != -1) return dp[x][y][idx];
        //현재 위치가 주어진 단어의 위치와 맞지 않는 경우 0 반환(유망x)
        if(board[x][y] != ansWord[idx]) return dp[x][y][idx] = 0;

        //0을 먼저 초기화 시키는 이유는 나아갈 수 있는 방향이 하나도 없을 경우 0을 리턴해야하기 때문이다.
        dp[x][y][idx] = 0;
        for(int i = 0; i < 4; i++) {
            for(int j = 1; j <= k; j++) {
                int xx = x + dx[i] * j;
                int yy = y + dy[i] * j;

                //다음 위치가 범위를 벗어나거나 유망하지 않은 경우는 통과시킨다.
                if(xx < 0 || yy < 0 || xx >= n || yy >= m || board[xx][yy] != ansWord[idx+1]) continue;
                //다음 위치가 유망한 경우 dfs를 통해 현재 위치를 메모이제이션 한다.
                dp[x][y][idx] += dfs(idx+1, xx, yy);
            }
        }

        return dp[x][y][idx];
    }
}

풀이를 보고도 어려운 문제였다. dfs + dp 를 사용한 문제였다. 그냥 bfs, dfs를 하면 시간초과를 맞게된다 ㅜ

 

문제의 핵심은 중복의 허용으로 인한 많은 연산량을 효율적으로 줄일지이다.

 

3차원 배열을 사용해서 메모이제이션을 한 이유는 주어진 영단어의 각 문자마다 그 위치에서 다른 방향의 유망성이 다르기 때문이다. 그러니 영단어의 길이만큼 2차원 배열을 만든다고 생각하면 편하다. 나도 3차원 배열은 처음써봐서 이해가 잘 안갔다..

 

-1 = 아직 방문 하지 않음

1 = 유망함

0 = 유망하지 않음

 

dp[i][j][k] = 상, 하, 좌, 우 별로 k만큼 이동할 수 있는 경우의 수 중 하나라도 유망하다면 1

                전부 유망하지 않다면 0

 

 

만약 BREAK 를 구할 때 BREAK를 이미 한번 구한 루트가 있을 때, BRE까지 구한 시점에서 현재 위치 x, y가 1로 dp[x][y][idx]에 메모이제이션 되어있다면 계속 전진하면서 중복되게 계산할 필요 없이 이미 유망하다는 것을 알기 때문에 바로 리턴을 해주면 되는 것이다.

 

만약 매개변수 idx에 주어진 인자값이 영단어의 길이와 같다는건 그전까지 계속해서 맞게 왔다는 뜻이므로 dp에 값을 1을 넣어주고 리턴하면 된다.

그리고 현재의 위치에 dp값이 -1이 아닌 경우는 이미 방문을 했다는 뜻 이므로 해당 dp값을 그대로 리턴해주면 된다.

그리고 현재의 위치에 있는 문자가 idx에 인자로 주어진 영단어의 문자위치와 값이 다를경우는 0을 리턴해주면 된다.

 

그리고 아직 현재위치 까지 유명하며 아직 메모이제이션이 안된 경우는 상, 하, 좌, 우 k만큼 갈 수 있는 경우의 수 만큼 다시 dfs를 해주면 된다.