이번 문제는 DP와 DFS를 활용하여 해결하였다. 우선 만들고자 하는 단어와 같은 좌표를 모두 start리스트에 저장하고, 3차원 리스트의 dp리스트를 만들었다. dp에는 해당 좌표와 해당 인덱스에서의 가짓수가 저장된다. DFS를 통해 탐색하며 dp리스트를 계속해서 갱신하고, 이를 통해 가짓수를 계속 더하여 값을 구하였다.

Code

n, m, k = map(int, input().split())
grid = [list(str(input())) for _ in range(n)]
word = list(str(input()))
dp = [[[-1 for _ in range(len(word))] for _ in range(m)] for _ in range(n)]
dy, dx = [0, 1, 0, -1], [1, 0, -1, 0]
start = []
answer = 0
for i in range(n):
    for j in range(m):
        if grid[i][j] == word[0]:
            start.append((i, j))
def dfs(y, x, idx):
    if idx == len(word):
        return 1
    if dp[y][x][idx] != -1:
        return dp[y][x][idx]
    dp[y][x][idx] = 0
    for i in range(4):
        for j in range(1, k+1):
            ny, nx = y+j*dy[i], x+j*dx[i]
            if 0 <= ny < n and 0 <= nx < m:
                if grid[ny][nx] == word[idx]:
                    dp[y][x][idx] += dfs(ny, nx, idx+1)
    return dp[y][x][idx]
for y, x in start:
    answer += dfs(y, x, 1)
print(answer)