[백준] 2186. 문자판

문제 링크

[백준] 2186. 문자판

풀이 과정

위의 예시에서 문자열 CAT을 만족시키는 경로는 총 9가지가 가능합니다.

같은 칸을 여러 번 방문할 수 있기 때문에, 좌표 (2, 1)에 위치한 A를 이용해 문자열을 만드는 경로 ⑤와 경로 ⑦이 가능하게 됩니다. 따라서, 이 문제는 방문 처리를 하는 배열 없이 탐색을 해야 되는 문제입니다.

또한, 위 경로 ⑤와 ⑦에서, 좌표 (2, 1)을 포함하는 그 이후의 경로는 동일한 것을 알 수 있습니다. 따라서, 임의의 좌표 (x, y) 이후의 진행 경로가 이전에 가봤던 경로일 경우, 이를 다시 탐색하는 데에 걸리는 시간을 단축시키기 위해 메모이제이션 기법이 사용됩니다.

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

for (int[][] arr : dp) {
    for (int[] arrr : arr) {
        Arrays.fill(arrr, -1);
    }
}

변수 target 은 맨 마지막으로 주어지는 영단어 입력을 의미합니다.

dp[i][j][k] 는 좌표 (i, j)에 영단어( target )의 k 번째 인덱스로 방문했을 시, 그 뒤로 만들어지는 경로들의 수를 의미합니다. 예를 들어, target 이 break 인 경우, dp[1][2][3] 은 좌표 (1, 2)에서 문자 a를 만나 만들 수 있는 경로들의 수를 나타냅니다.

for (int[][] arr : dp) {
    for (int[] arrr : arr) {
        Arrays.fill(arrr, -1);
    }
}

각 좌표에서의 가능한 경로의 수가 0이 될 수 있기 때문에, 이와 구분되는 초기화가 필요했습니다. 위 코드는 3차원 배열의 모든 요소를 -1로 초기화 합니다.

for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
        if (map[i][j] == target[0]) {
            answer += dfs(i, j, 0);
        }
    }
}

모든 좌표를 돌며, 시작 문자가 타겟 문자열의 첫 번째 문자와 맞다면 DFS 탐색을 실행합니다. 그리고 반환된 경로 가짓수를 answer 변수에 누적시킵니다.

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

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

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

            if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
            if (map[nx][ny] == target[now + 1]) dp[x][y][now] += dfs(nx, ny, now + 1);
        }
    }

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

dfs 메소드 는 좌표 (x, y)의 now 번째 문자로 이어지는 가능한 경로의 수를 리턴합니다.

• if (dp[x][y][now] != -1) return dp[x][y][now]; : 처음에 초기화 한 -1 값과 다르다면, 좌표 (x, y) 에 위치한 문자 이후로 경로를 만들어 본 적이 있기 때문에, 그 값을 가져다 씁니다.
• if (now == target.length - 1) return dp[x][y][now] = 1; : 타겟 문자열을 만들었으므로 가능한 경로가 됩니다. 따라서, 경로가 하나 추가됬음을 의미하도록 1을 리턴시킵니다.
• 이제 상하좌우 네 방향에 대해 1부터 K만큼 이동시켜 봅니다. 이동된 좌표에 다음 번에 와야할 문자가 위치한다면, dfs 메소드 를 호출해 이동된 좌표를 시작으로 가능한 경로를 만들어 봅니다. 또한, 가능한 경로의 가짓수를 의미하는 리턴 값을 dp 요소에 누적하여 저장해 줍니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int N, M, K;
    static char[][] map;
    static int[][][] dp;
    static boolean[][] visit;
    static int[] dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1};
    static char[] target;

    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];
        visit = new boolean[N][M];
        int answer = 0;

        for (int i = 0; i < N; i++) {
            String s = br.readLine();
            for (int j = 0; j < M; j++) {
                map[i][j] = s.charAt(j);
            }
        }

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

        for (int[][] arr : dp) {
            for (int[] arrr : arr) {
                Arrays.fill(arrr, -1);
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == target[0]) {
                    answer += dfs(i, j, 0);
                }
            }
        }

        System.out.println(answer);
    }

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

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

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

                if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
                if (map[nx][ny] == target[now + 1]) dp[x][y][now] += dfs(nx, ny, now + 1);
            }
        }

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