[백준 / python] 2186: 문자판

문제

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

출력

첫째 줄에 경로의 개수를 출력한다. 이 값은 231-1보다 작거나 같다.

풀이

dfs + dp문제

import sys

sys.setrecursionlimit(10 ** 5)
dirs = ((0, 1), (0, -1), (1, 0), (-1, 0))
N, M, K = map(int, sys.stdin.readline().split())
board = [list(sys.stdin.readline().strip()) for _ in range(N)]
word = sys.stdin.readline().strip()
result = 0
dp = [[[-1] * M for _ in range(N)] for _ in range(len(word) + 1)]

def dfs(r, c, cur_word, depth):
    if depth == len(word):
        return 1
    if dp[depth][r][c] != -1:
        return dp[depth][r][c]
    count = 0
    for dir_r, dir_c in dirs:
        for m in range(1, K + 1):
            new_r, new_c = r + (dir_r * m), c + (dir_c * m)
            if not 0 <= new_r < N or not 0 <= new_c < M:
                continue
            next_word = cur_word + board[new_r][new_c]
            if next_word != word[:depth + 1]:
                continue
            count += dfs(new_r, new_c, next_word, depth + 1)
    dp[depth][r][c] = count
    return count

for i in range(N):
    for j in range(M):
        if board[i][j] == word[0]:
            result += dfs(i, j, word[0], 1)

print(result)