[Java] 백준 2186 문자판

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

난이도

골드3

문제

알파벳 대문자가 한 칸에 한 개씩 적혀있는 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자 이하의 영단어가 주어진다. 모든 문자들은 알파벳 대문자이며, 공백 없이 주어진다.

출력

첫째 줄에 경로의 개수를 출력한다. 이 값은 231-1보다 작거나 같다.

내 코드

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

public class Main {
    static int N, M, K;
    static char[][] map;
    static String word;
    static int[][][] dp;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -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 char[N][M];
        for (int i = 0; i < N; i++) {
            map[i] = br.readLine().toCharArray();
        }

        word = br.readLine();
        dp = new int[N][M][word.length()];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                Arrays.fill(dp[i][j], -1);
            }
        }

        int ans = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == word.charAt(0)) {
                    ans += dfs(i, j, 0);
                }
            }
        }

        System.out.println(ans);
    }

    public static int dfs(int x, int y, int idx) {
        if (idx == word.length() - 1) return 1;
        if (dp[x][y][idx] != -1) return dp[x][y][idx];

        dp[x][y][idx] = 0;

        for (int d = 0; d < 4; d++) {
            for (int k = 1; k <= K; k++) {
                int nx = x + k * dx[d];
                int ny = y + k * dy[d];

                if (!inRange(nx, ny) || map[nx][ny] != word.charAt(idx + 1)) {
                    continue;
                }

                dp[x][y][idx] += dfs(nx, ny, idx + 1);
            }
        }

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

    public static boolean inRange(int x, int y) {
        return 0 <= x && x < N && 0 <= y && y < M;
    }
}

DFS는 최악의 경우 완탐과 동일하기 때문에 시간초과 혹은 메모리 초과가 발생할수도 있는데, 이 문제는 DFS + DP를 결합하여 메모이제이션을 적용해야한다.

dp[x][y][idx]는 idx번째 문자까지 만든 경우의 수를 저장하여 중복 계산을 방지한다. 값이 -1이라면 아직 방문하지 않은 상태이기 때문에 DFS를 진행하고, 값이 0이상이라면 해당 값을 반환하여 불필요한 탐색을 제외한다.

원래는 record를 선언해서 단어의 각 알파벳마다의 위치를 저장했는데 이런 이유로 메모리 초과가 발생했던 것 같다.