[2418] 단어 격자

[2418] 단어 격자

---

아래와 같은 단어격자가 주어진다.

이 격자내에서 읽을 수 있는 단어가 주어지면 주어진 단어를 읽을 수 있는 경우의 수를 출력하는 문제이다.

(중복해서 칸을 이동하며 읽을 수 있고, 칸은 대각선, 아래, 위, 좌, 우 를 포함 8방향을 이동할 수 있다)

1) 메모이제이션 + 완전탐색

각 단어격자의 문자를 시작 문자로 하여 주어진 단어를 만들 수 있는지 모두 체크한다.

#include <cstdio>
using namespace std;
 
char puzzle[201][201], word[101];
long long ans = 0; int l;
long long d[201][201][101];
 
long long findword(int y, int x, int h, int w, int i){
    if(i >= l){
        return 1;
    }
    if(d[y][x][i] != -1) return d[y][x][i];
    int dx[] = {0, 1, 1, 1, 0, -1, -1, -1}, dy[] = {-1, -1, 0, 1, 1, 1, 0, -1};
    long long ret = 0;
    for(int k = 0; k < 8; k++){
        int ny = y + dy[k], nx = x + dx[k];
        if(0 <= ny && ny < h && 0 <= nx && nx < w && puzzle[ny][nx] == word[i]){
            ret += findword(ny, nx, h, w, i+1);
        }
    }
    return d[y][x][i] = ret;
}
 
int main(){
    int h, w;
    scanf("%d %d %d", &h, &w, &l);
    for(int i = 0; i < h; i++) for(int j = 0; j < w; j++){
        scanf(" %c",&puzzle[i][j]);
        for(int k = 0; k < l; k++) d[i][j][k] = -1;
    }
    for(int i = 0; i < l; i++) scanf(" %c", &word[i]);
    for(int i = 0; i < h; i++) for(int j = 0; j < w; j++){
        if(puzzle[i][j] == word[0]){
            ans += findword(i, j, h, w, 1);
        }
    }
    printf("%lld\n",ans);
}
 

2) 다 풀고나서 다른사람의 코드를 보던 중 배울 점이 많아서 가져왔다. (cubelover님 코드)

사실 주어진 단어의 길이가 L이면 위에 방식은 1부터 L까지 보면서 모든 경우를 저장하는 방식이다.

그래서 dp[i][j][k] 가 단어격자 (i, j) 에서 길이 k-1까지 읽었을 때 나머지 단어를 읽을 수 있는 경우의 수를 담도록 설계하였다.

하지만 아래의 코드 같은 경우 두 가지 차이점이 존재한다.

1 - 재귀적으로 하지 않고, loop를 통해서 구현

2 - 모든 길이에 대해 저장하지 않고 바로 이전 길이에 대해서만 저장하면 다음 길이의 경우의 수가 보장

생각해보면 첫 번째 글자가 일치하는지 보고, 그 다음 두번째 글자가 일치하는지 보고, 그 다음 세번째 글자가 일치하는지 보는 방식이므로,

각 경우에 대하여 필요한 정보는 해당 단어의 8방향에서 이전 길이까지 읽은 경우의 수만 필요하다. 따라서 모든 길이에 대한 dp를 저장하지 않아도 된다.

#include <cstdio>
 
char a[202][202];
char s[101];
long long d[2][202][202];
 
int main()
{
    long long r = 0;
    int p, q;
    int i, j, k, l, m, n;
    scanf("%d%d%d", &n, &m, &l);
    for (i = 0; i < n; i++) scanf("%s", a + i);
    scanf("%s", s);
    for (i = 0; i < n; i++) for (j = 0; j < m; j++) if (a[i][j] == *s) d[0][i][j] = 1;
    for (k = 1; k < l; k++) for (i = 0; i < n; i++) for (j = 0; j < m; j++)
    {
        // 업데이트 할 값 초기화, 이전 길이까지의 값은 d[!(k&1)][i][j]에 가지고 있다.
        d[k & 1][i][j] = 0;
        if (a[i][j] == s[k]) {
            // 8방향을 나타내는 for문이다. 이런 방법은 알아두자!
            for (p = -1; p <= 1; p++) for (q = -1; q <= 1; q++) {
                if ((p || q) && i + p >= 0 && i + p < n && j + q >= 0 && j + q < m)
                    d[k & 1][i][j] += d[!(k & 1)][i + p][j + q];
            }
    }
    for (i = 0; i < n; i++) for (j = 0; j < m; j++) r += d[!(l & 1)][i][j];
    printf("%lld", r);
}