10월 21일 - 유니콘

오늘의 TIL에서는 체스판에서 유니콘이 특정 단어를 찾는 문제를 해결하기 위한 DP(Dynamic Programming) 알고리즘을 작성해 보았다. 이 코드는 유니콘의 움직임을 기반으로 단어를 찾는 경로의 경우의 수를 계산하는 프로그램이다. 문제는 유니콘이 나이트와는 다른 방식으로 움직이는 것에 기반해 복잡한 경로를 탐색하는 것에 초점이 있다.

문제
유니콘은 체스에서 나이트와 비슷한 말이다. 단, 나이트는 두 칸을 한 방향으로 움직이고, 또 다른 한 칸을 다른 방향으로 움직이지만, 유니콘은 두 칸보다 많은 칸을 한 방향으로 움직이고, 한 칸보다 많은 칸을 또다른 방향으로 움직인다.
좀 더 정확하게 유니콘이 움직이는 방법을 살펴보면 다음과 같다.
유니콘을 든다.
유니콘을
$4$개의 기본 방향 중 하나로 두 칸보다 많이 움직인다.
유니콘을 방금 움직인 방향과 수직인 방향
$2$개 중 하나로 한 칸보다 많이 움직인다.
유니콘을 놓는다.
체스판의 크기는
$N \times M$이다. 체스판의 각 칸에는 알파벳 대문자의 처음
$L$개의 문자 중 하나가 쓰여 있다.
$N$,
$M$,
$L$, 그리고 단어가 주어진다. 유니콘이 움직인 경로 (유니콘을 놓은 곳)가 입력으로 주어진 단어와 일치하는 경우의 수를 출력하는 프로그램을 작성하시오.

입력
첫째 줄에
$N$,
$M$,
$L$이 주어진다.
$N$과
$M$은
$300$보다 작거나 같은 자연수이다.
$L$은
$26$보다 작거나 같은 자연수이다. 둘째 줄에 단어가 주어진다. 단어의 길이는 최대
$50$이며, 알파벳 대문자로만 이루어져 있다. 셋째 줄 부터
$N$개의 줄에 체스판에 쓰여 있는 단어가 주어진다.

출력
첫째 줄에 경로를
$1\,000\,000\,007$로 나눈 나머지를 출력한다.

예제 입력 1
3 4 2
AB
ABBA
AAAA
BBBB
예제 출력 1
2
예제 입력 2
5 5 2
CD
ABBAA
AAABB
BBBBB
ABABA
ABBBB
예제 출력 2
0
예제 입력 3
4 4 1
AA
AAAA
AAAA
AAAA
AAAA
예제 출력 3
20
예제 입력 4
4 4 1
AAAAA
AAAA
AAAA
AAAA
AAAA
예제 출력 4
172
예제 입력 5
1 1 5
ABCDE
C
예제 출력 5
0
예제 입력 6
8 8 26
TOPCODER
AILFPSPF
DZIOMYCE
QOODZARU
YVOTLTRX
LSRIGANL
LCIUUSNF
IWVXKTDE
OVPPNXRD
예제 출력 6
1
예제 입력 7
20 20 2
AAAAA
ABBAAAAABBBBBBBABABA
ABBBBBABAAAABBAAABAA
BAAABAABAABBABABBABB
BBABBAAAABABAAAAABBA
BBABAABABBAABABABBBA
BABABAABABBBABBAABBA
BAABBAAABBBABBABAAAA
BAABBBBABAABAAAAABAA
AABABAAAAABBBABABBBA
BBAABAAABBAABAAAAABA
BAAAAABABBAAABABABBA
ABBAABBBABABBABAAABB
AAAABAAAAAAAABBBAABB
AAABABAAAAAABAAABABB
AAABABABBABABAAABBBA
AAABBBBAABBAABAAABBA
BBBBAAABBABABAAAABAB
BBAABBAABAAAABAABABA
BBBAABBABABBBBBBBBBA
AAABABBBBAABABBBBBBB
예제 출력 7
373977054

코드 설명

우선, 코드의 핵심은 DP 배열을 사용하여 각 글자에 대한 경로를 누적적으로 계산하는 것이다. 이를 통해 체스판에서 주어진 단어가 완성되는 모든 가능한 경로를 구할 수 있다.

입력 설명

첫 번째 입력으로는 체스판의 크기 N(행), M(열), 그리고 사용되는 알파벳의 개수 L이 주어진다. 그 다음에는 찾고자 하는 단어가 입력되며, 이후에는 N개의 줄에 걸쳐 체스판의 문자들이 주어진다.

코드 구현

import java.util.Scanner;

public class Main {
    static final int MOD = 1000000007;
    static long[][][] dp = new long[50][301][301];
    static char[] str = new char[51];
    static char[][] board = new char[301][301];
    static int n, m, l;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt(); // 체스판의 행 개수
        m = sc.nextInt(); // 체스판의 열 개수
        l = sc.nextInt(); // 사용되는 알파벳 개수
        String word = sc.next(); // 찾으려는 단어
        str = word.toCharArray();

        // 체스판 입력 받기
        for (int i = 0; i < n; i++) {
            board[i] = sc.next().toCharArray();
        }

        // 첫 번째 글자에 대한 초기화
        for (int j = 1; j <= n; ++j) {
            for (int k = 1; k <= m; ++k) {
                dp[0][j][k] = dp[0][j - 1][k] + dp[0][j][k - 1] - dp[0][j - 1][k - 1];
                if (board[j - 1][k - 1] == str[0]) {
                    dp[0][j][k]++;
                }
            }
        }

        // 두 번째 글자부터 단어 끝까지 DP 수행
        for (int i = 1; i < word.length(); ++i) {
            for (int j = 1; j <= n; ++j) {
                for (int k = 1; k <= m; ++k) {
                    if (board[j - 1][k - 1] == str[i]) {
                        dp[i][j][k] = sum(i - 1, 1, 1, n, m);
                        dp[i][j][k] -= sum(i - 1, 1, k - 1, n, k + 1);
                        dp[i][j][k] -= sum(i - 1, j - 1, 1, j + 1, m);
                        dp[i][j][k] -= sum(i - 1, j - 2, k - 2, j + 2, k + 2);
                        dp[i][j][k] += sum(i - 1, j - 2, k - 1, j + 2, k + 1);
                        dp[i][j][k] += sum(i - 1, j - 1, k - 2, j + 1, k + 2);
                    }
                    dp[i][j][k] += dp[i][j - 1][k];
                    dp[i][j][k] += dp[i][j][k - 1];
                    dp[i][j][k] -= dp[i][j - 1][k - 1];
                    dp[i][j][k] = (dp[i][j][k] + 2L * MOD) % MOD;
                }
            }
        }

        System.out.println(dp[word.length() - 1][n][m]);
        sc.close();
    }

    static int sum(int ind, int a, int b, int c, int d) {
        if (a < 1) a = 1;
        if (b < 1) b = 1;
        if (c > n) c = n;
        if (d > m) d = m;
        long ret = 0;
        ret += dp[ind][c][d];
        ret -= dp[ind][a - 1][d];
        ret -= dp[ind][c][b - 1];
        ret += dp[ind][a - 1][b - 1];
        ret = (ret + 2L * MOD) % MOD;
        return (int) ret;
    }
}

주요 알고리즘 설명

1. dp 배열 초기화: dp[0][j][k]는 첫 번째 글자를 찾을 수 있는 좌표를 저장한다. 이때, 주어진 체스판에서 첫 글자와 일치하는 좌표를 찾아 초기값을 설정한다.

2. 동적 계획법(DP) 적용: 두 번째 글자부터 단어의 끝까지 DP를 수행한다. 이때, 이전 글자의 위치를 기반으로 다음 글자의 위치를 찾기 위해 sum 함수를 활용한다. sum 함수는 좌표 범위 내에서 누적합을 계산해 유니콘의 이동 경로를 추적하는데 사용된다.

3. 경로 누적 계산: dp[i][j][k]는 현재 글자가 체스판의 (j, k) 좌표에서 시작하는 경로 수를 의미한다. 이를 통해 각 글자마다 유효한 경로를 계속 누적해 나간다.

4. 결과 출력: 마지막으로 dp 배열의 마지막 값에서 찾은 경로의 개수를 출력한다. 이 값은 매우 큰 숫자가 될 수 있기 때문에, MOD = 1000000007로 나눈 나머지를 반환한다.

So...

이 코드의 핵심은 다중 차원의 DP 배열을 사용해 유니콘이 이동 가능한 경로를 추적하며 주어진 단어를 찾는 모든 경우의 수를 계산하는 것이다. DP 배열을 통해 이전 경로들을 효율적으로 계산하여, 체스판의 크기가 커져도 성능을 최적화할 수 있게 설계되었다.