[ BOJ ][JAVA][2186] 문자판

www.acmicpc.net/problem/2186

2186번: 문자판

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	5181	1090	726	21.372%

문제

알파벳 대문자가 한 칸에 한 개씩 적혀있는 N×M 크기의 문자판이 있다. 편의상 모든 문자는 대문자라 생각하자. 예를 들어 아래와 같은 문자판을 보자.

K	A	K	T
X	E	A	S
Y	R	W	U
Z	B	Q	P

이 문자판의 한 칸(아무 칸이나 상관없음)에서 시작하여 움직이면서, 그 칸에 적혀 있는 문자들을 차례대로 모으면 하나의 단어를 만들 수 있다. 움직일 때는 상하좌우로 K개의 칸까지만 이동할 수 있다. 예를 들어 K=2일 때 아래의 그림의 가운데에서는 'X' 표시된 곳으로 이동할 수 있다.

		X
		X
X	X		X	X
		X
		X

반드시 한 칸 이상 이동을 해야 하고, 같은 자리에 머물러 있을 수 없다. 또, 같은 칸을 여러 번 방문할 수 있다.

이와 같은 문자판과 K, 그리고 하나의 영단어가 주어졌을 때, 이와 같은 영단어를 만들 수 있는 경로가 총 몇 개 존재하는지 알아내는 프로그램을 작성하시오.

위의 예에서 영단어가 BREAK인 경우에는 다음과 같이 3개의 경로가 존재한다. 앞의 수는 행 번호, 뒤의 수는 열 번호를 나타낸다.

• (4, 2) (3, 2) (2, 2) (1, 2) (1, 1)
• (4, 2) (3, 2) (2, 2) (1, 2) (1, 3)
• (4, 2) (3, 2) (2, 2) (2, 3) (1, 3)

입력

첫째 줄에 N(1 ≤ N ≤ 100), M(1 ≤ M ≤ 100), K(1 ≤ K ≤ 5)가 주어진다. 다음 N개의 줄에는 M개의 알파벳 대문자가 주어지는데, 이는 N×M 크기의 문자판을 나타낸다. 다음 줄에는 1자 이상 80자 이하의 영단어가 주어진다. 모든 문자들은 알파벳 대문자이며, 공백 없이 주어진다.

출력

첫째 줄에 경로의 개수를 출력한다. 이 값은 int 범위이다.

예제 입력 1

4 4 1
KAKT
XEAS
YRWU
ZBQP
BREAK

예제 출력 1

3

코드

// dp + dfs
import java.io.*;
import java.util.*;

public class p2186 {
    static BufferedReader br;
    static StringTokenizer st;
    static int n, m, k, cnt;
    static int[] dr = {1, 0, -1, 0};
    static int[] dc = {0, 1, 0, -1};
    static int dp[][][];
    static char map[][];
    static boolean visit[][];
    static String target = "";
    public static void main(String[] args) throws Exception {
        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());

        cnt = 0;
        map = new char[n][m];

        for (int i = 0; i < n; i++) {
            String line = br.readLine();
            for (int j = 0; j < m; j++) {
                map[i][j] = line.charAt(j);
            }
        }

        target = br.readLine();
        dp = new int[n][m][target.length()];

        // -1로 싹 다 초기화
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                for (int q = 0; q < target.length(); q++) {
                    dp[i][j][q] = -1;
                }
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                cnt += dfs(i, j, 0);
            }
        }

        System.out.println(cnt);
    }

    // r, c 에서 출발하는데 target i번째 문자로 탐색을 했을 때 가능한 경우의 수 를 메모이제이션한다.
    static int dfs(int r, int c, int index) {
        if (index == target.length() - 1) { // 마지막 문자
            return dp[r][c][index] = 1;
        }
        if (dp[r][c][index] != -1) {    // 이미 존재할 때
            return dp[r][c][index];
        }
        if (map[r][c] != target.charAt(index)) {
            return dp[r][c][index] = 0;
        }

        dp[r][c][index] = 0;

        // 사방으로 move 만큼 다음문자 탐색 -> 있으면 dp에 이전 값 만큼 더해준다.
        for (int d = 0; d < 4; d++) {
            for (int move = 1; move <= k; move++) {
                int nr = r + dr[d] * move;
                int nc = c + dc[d] * move;

                if(nr < 0 || nr >= n || nc < 0 || nc >= m || map[nr][nc] != target.charAt(index + 1)) continue;

                dp[r][c][index] += dfs(nr, nc, index + 1);
            }
        }

        return dp[r][c][index];
    }
}