[백준] 2418 : 단어 격자

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

2418번: 단어 격자

---

• 문제에서도 명시돼있듯 정답의 최대값이 10^18 은 된다는 것만 봐도 일단 단순한 그래프 탐색은 불가능하다.
• 중복해서 문자를 사용할 수 있기 때문에, 모든 문자가 같은 상태라면 최대 8^100 이다...
• 따라서 DP 배열을 사용해야 하는데, 처음에는 각 위치별로 자기 주변 알파벳 각각의 개수를 담으려고 했다.
• T 주변의 A 개수, A 주변의 R 개수, R 주변의 T 개수를 차례대로 곱해 나가려고 생각했지만, 같은 알파벳이더라도 위치에 따라서 다음 문자의 개수가 달라지기 때문에 불가능하고, 결국 완전 탐색과 같아지게 된다.
• DP 배열을, 각 위치별로 i 번째 문자부터 끝문자까지 가능한 경우의 수를 담아주면 풀 수 있다.
• 예를 들어 T 주변에 있는 A 를 전부 볼 경우, 여러 A들 중 하나의 위치가 (3, 3) 이라고 하면, DP[3][3][1] 의 값은 가능한 모든 ARTU 의 경우의 수이다.
• 그렇게 되면 T 주변의 A 들에 대해 각각의 dp 값들을 더해주면 해당 위치에서 T 의 가능한 경우의 수가 나온다.
• 이 연산을 재귀적으로 반복한다면 1번째 위치에서 가능한 T 의 경우의 수, 2번쨰 A 의 경우의 수 ... 등등이 각각 dp 배열에 저장되며, 다른 T 에서 시작하더라도 같은 A 에 접근 시 기존에 구했던 값을 재사용하기만 하면 된다.

---

#include <iostream>

#define ull unsigned long long

using namespace std;

int H, W, L;
char grid[200][200];
pair<int,int> dir[8] = {{-1,0},{1,0},{0,-1},{0,1},{-1,-1},{-1,1},{1,1},{1,-1}}; // 8방향
string target;
ull dp[200][200][100];
ull answer;

void dfs(int r, int c, int depth)                   // 이번 depth(단어 인덱스) 에 맞는 dp 값
{
    if(depth == L-1)
    {
        dp[r][c][depth] = 1;
        return;
    }

    ull value = 0;                                  // 이번 dp 값을 담을 변수
    for(int i = 0 ; i < 8 ; i++)
    {
        int nr = r + dir[i].first;
        int nc = c + dir[i].second;
        if(nr >= 0 && nr < H && nc >= 0 && nc < W)  // 8방향에 대해서 검사하면서
        {
            if(grid[nr][nc] == target[depth+1])     // 알맞은 문자열이 나온다면
            {
                if(dp[nr][nc][depth+1] == -1)       // 이전에 방문하지 못했던 위치일 경우에만
                {
                    dfs(nr, nc, depth+1);           // dfs 새로 탐색해주고
                }
                value += dp[nr][nc][depth+1];       // 기존에 방문했거나 새로 탐색 완료한 dp 값을 총합에 더해줌
            }
        }
    }

    dp[r][c][depth] = value;                        // 이번 dp 값 업데이트
}

int main(void)
{
    cin >> H >> W >> L;
    for(int r = 0 ; r < H ; r++)
    {
        for(int c = 0 ; c < W ; c++)
        {
            cin >> grid[r][c];
            for(int i = 0 ; i < 100 ; i++) dp[r][c][i] = -1;    // dp 배열 -1 로 초기화
        }
    }
    cin >> target;
    
    for(int r = 0 ; r < H ; r++)
    {
        for(int c = 0 ; c < W ; c++)
        {
            if(grid[r][c] == target[0])                         // 가능한 모든 단어 시작 지점부터 dfs 탐색
            {
                dfs(r, c, 0);
                answer += dp[r][c][0];
            }
        }
    }

    cout << answer << endl;
}