[BOJ] 2186. 문자판

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

접근 방법

처음에 문제를 보고 BFS , DFS 로 설계하면 되겠다고 생각을 하였다.

하지만 BFS로 풀 경우 메모리초과와 시간초과가 나와서 DFS+DP 로 풀게 되었다.

먼저 DFS로 탐색을 하면서 그 때 마다 나올 수 있는 경우를 메모이제이션 해주었다.

int dfs(int x, int y, int words) 에서 x와 y는 위치를 뜻하고 words는 찾아줘야할 단어의 인덱스로 지정해주었다.

static int[][][] dp 는 각각의 위치에서 몇 번째 단어가 되었을 때 끝까지 갈 경우의 수를 저장해주었다.

만약 dp[1][1][2] = 3 이면 (1,1)에서 3번째 단어의 문자는 전체 단어를 만드는 경우의 수는 3개라 표현할 수 있다.

이렇게 하면 무엇이 좋냐고 물었을 때, 예를 들어보겠다.

---

 

이렇게 배열이 있을 때 ABCDE 라는 문자열을 찾을 때

시작점은 (2,0) (2,2) (3,1) 이 될 수 있다.

먼저 (2,0)부터 시작을 하면

(2,0) → (2,1) → (1,1) → (0,1) → (0,2)

(2,0) → (2,1) → (1,1) → (1,2) → (0,2)

(2,0) → (3,0) → X

이제 (3,1)를 봐보자.

(3,1) → (2,1) → (1,1) → (0,1) → (0,2)

(3,1) → (2,1) → (1,1) → (1,2) → (0,2)

(3,1) → (3,0) → X

이제 우리가 (2,0)이라는 위치에 들어가면 ABCDE라는 단어를 찾을 때와

(3,1) 에서 출발을 했을 때 탐색을 하게 될 때 (2,1)을 만나고 탐색을 하게 될 때 중복이 일어나는

것을 알 수 있다.

그렇기 때문에 우리가 (2,1)에서 ABCDE 단어를 만들 수 있는 경우의 수를 담게 된다면 우리는 그 시간을 줄일 수 있을 것이다.

Need Know

1. DFS
2. DP

전체 코드 ( Java )

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

class Main{
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N;
    static int M;
    static int K;
    static char[][] map;
    static int[][][] dp;
    static String word;
    static int ans = 0;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    public static void main(String[] args) throws IOException {
        set();
        solve();
        bw.flush();
        bw.close();
        br.close();
    }
    static void set() throws IOException {
        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++){
            String str = (br.readLine());
            for(int k=0; k<M; k++){
                map[i][k] = str.charAt(k);
            }
        }
        word = br.readLine();
        dp = new int[N][M][word.length()];
        for(int i=0; i<N; i++){
            for(int k=0; k<M; k++){
                for(int z = 0; z<word.length(); z++){
                    dp[i][k][z] = -1;
                }
            }
        }
    }
    static void solve() throws IOException {
        for(int i=0; i<N; i++){
            for(int k=0; k<M; k++){
                if(map[i][k] == word.charAt(0)){
                    ans+= dfs(i,k,0);
                }
            }
        }
        bw.write(ans+"");
    }
    static int dfs(int x, int y, int words) {
        if (words == word.length() - 1) {
            return 1;
        }
        if (dp[x][y][words] != -1) {
            return dp[x][y][words];
        }
        dp[x][y][words] = 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 (nx >= N || ny >= M || nx < 0 || ny < 0) continue;
                if (map[nx][ny] == word.charAt(words + 1)) {
                    dp[x][y][words] += dfs(nx, ny, words + 1);
                }
            }
        }
        return dp[x][y][words];
    }
}