백준 2186 문자판

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

dfs를 통해 문자열의 크기와 같다면 return해주는 문제이다.

당연히 단순 dfs만 해주면 시간초과가 발생한다

• dfs만 사용한 코드

n,m,k = list(map(int,input().split()))
arr = []
for i in range(n):
    row = list(input())
    arr.append(row)
cmp = list(input())
start = []
for i in range(n):
    for j in range(m):
        if arr[i][j] == cmp[0]:
            start.append((i,j))
dx = [-1,0,1,0]
dy = [0,1,0,-1]
ans = 0
def dfs(x,y,depth):
    global ans
    if depth == len(cmp)-1:
        ans += 1
        return
    tmp = cmp[depth+1]
    for i in range(1,k+1):
        for j in range(4):
            nx = x + i * dx[j]
            ny = y + i * dy[j]
            if 0 <= nx < n and 0 <= ny < m and arr[nx][ny] == tmp:
                dfs(nx,ny,depth+1)

for st in start:
    x,y = st
    dfs(x,y,0)
print(ans)

그렇기 때문에 중복을 제거해 주어야 되는데, 잘 생각해보면
만약 내가 BREAK를 구성하는데, 앞에는 구성이 되었고, E를 밟았는데, 그 뒤로 BREAK를 구성할 수 있는 개수만 구해주면, 3번째차례에 E를 밟았을때는 다시 계산을 해주지 않아도 된다.
즉 dp를 구성해 위치 + 현재 인덱스를 통해 상태값을 저장해 놓는다.

초기값을 만약 0으로 구성한다면, 해당 위치가 방문은 했지만 경로가 없는것인지, 아직 방문하지 않은것인지 상태가 중복되기 때문에,
초기값을 -1로 구성해주고, 방문 후 경우의수가 존재하지 않을 때 에는 0으로 바꾸어 주어야 한다.

import sys
input = sys.stdin.readline
n,m,k = list(map(int,input().strip().split()))
arr = []
for i in range(n):
    row = list(input().strip())
    arr.append(row)
cmp = list(input().strip())
start = []
for i in range(n):
    for j in range(m):
        if arr[i][j] == cmp[0]:
            start.append((i,j))
dx = [-1,0,1,0]
dy = [0,1,0,-1]
dp = [[[-1]*len(cmp) for i in range(m)] for i in range(n)]
ans = 0
def dfs(x,y,depth):
    global ans
    if dp[x][y][depth] != -1:
        return dp[x][y][depth]
    if depth == len(cmp)-1:
        return 1
    dp[x][y][depth] = 0
    for i in range(1,k+1):
        for j in range(4):
            nx = x + i * dx[j]
            ny = y + i * dy[j]
            if 0 <= nx < n and 0 <= ny < m and arr[nx][ny] == cmp[depth+1]:
                    dp[x][y][depth] += dfs(nx,ny,depth+1)
    return dp[x][y][depth]

for st in start:
    x,y = st
    ans += dfs(x,y,0)
print(ans)