[BOJ] 2186 - 문자판 (Python)

 

 

아이디어

 

DFS로 경로의 수를 계산하되, 동적 계획법으로 이미 방문한 칸의 이후 경로의 수는 저장하여 빠르게 계산한다.

 

 

풀이

 

import sys

input = sys.stdin.readline

def dfs(idx, r, c):
    if dp[r][c][idx] >= 0:
        return dp[r][c][idx]
    if board[r][c] != word[idx]:
        dp[r][c][idx] = 0
        return 0
    if idx == 0:
        dp[r][c][idx] = 1
        return 1
    dp[r][c][idx] = 0
    for k in range(-K, K+1):
        if k:
            nr, nc = r+k, c+k
            if N > nr >= 0:
                dp[r][c][idx] += dfs(idx-1, nr, c)
            if M > nc >= 0:
                dp[r][c][idx] += dfs(idx-1, r, nc)
    return dp[r][c][idx]

N, M, K = map(int, input().split())
board = [tuple([*input().rstrip()]) for _ in range(N)]
word = input().rstrip()
W = len(word)
dp = [[[-1]*W for _ in range(M)] for _ in range(N)]
res = 0
for r in range(N):
    for c in range(M):
        if board[r][c] == word[-1]:
            res += dfs(W-1, r, c)
print(res)

 

 

단어 인덱스를 0부터 증가시키는 코드는 35배 이상 느렸다.
정확한 이유는 잘 모르겠으나 아무래도 테스트 케이스의 차이인 듯하다.

# 더 느린 코드
...
res = 0
for r in range(N):
    for c in range(M):
        if board[r][c] == word[0]:
            res += dfs(0, r, c)
print(res)