백준 - 그림판 2186(DP, 그래프, 골3)

문제 풀러가기
동적계획법 원리 알아보기

해당 문제는 봤을 때 단순히 그래프 탐색 같지만, 문제에서 주어진 예시를 보면 동적계획법으로 풀어야 함을 눈치 챌 수 있다. 그 이유는 부분 문제가 반복되는 걸 확인할 수 있기 때문이다.

따라서 다음과 같이 식을 구성할 수 있다.
DP[i][j][k] = MAPS(i,j)의 알파벳이 target의 K번 째 알파벳일 때 만들 수 있는 경우의 수

예를 들면 DP[1][2][2] 가 의미하는 바는 BRE까지 만들었을 때 (1,2)위치에 있는 알파벳 E에서 부터 앞으로 만들 수 있는 경우의 수를 의미한다. 여기서는 3을 의미한다.

코드를 보면 다음과 같다.

import sys

N, M, K = map(int, sys.stdin.readline().strip().split(' '))
MAPS = [list(sys.stdin.readline().strip()) for _ in range(N)]
TARGET = list(sys.stdin.readline().strip())

dp = [[[-1 for _ in range(len(TARGET))] for _ in range(M)] for _ in range(N)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]


def dfs(x, y, depth):

    if dp[x][y][depth] != -1: // 이미 방문 했다면 바로 return
        return dp[x][y][depth]

    dp[x][y][depth] = 0 // 방문하지 않았다면 0으로 초기화 하고 계산
    if MAPS[x][y] == TARGET[depth]: // 애초에 같지 않으면 경우의 수 0
        if depth == len(TARGET) - 1:
            dp[x][y][depth] = 1
            return 1 // 기저 사건 (가장 basic한 사건)
        else:
            for k in range(1, K + 1):
                for i in range(4):
                    nx, ny = x + dx[i]*k, y + dy[i]*k
                    if 0 <= nx < N and 0 <= ny < M:
                        dp[x][y][depth] += dfs(nx, ny, depth + 1)

    return dp[x][y][depth]


ret = 0
for i in range(N):
    for j in range(M):
        ret += dfs(i, j, 0)
print(ret)