BOJ 2186 문자판

https://www.acmicpc.net/problem/2186
시간 2초, 메모리 128MB
input :

• N(1 ≤ N ≤ 100), M(1 ≤ M ≤ 100), K(1 ≤ K ≤ 5)
• M개의 알파벳 대문자가 주어지는데, 이는 N×M 크기의 문자판
• 1자 이상 80자 이하의 영단어가 주어진다. 모든 문자들은 알파벳 대문자이며, 공백 없이 주어진다.

output :

• 경로의 개수를 출력

조건 :

• 움직일 때는 상하좌우로 K개의 칸까지만 이동
• 반드시 한 칸 이상 이동을 해야 하고, 같은 자리에 머물러 있을 수 없다.
• 같은 칸을 여러 번 방문할 수 있다.

---

오늘도 공부의 날인거 같다... 어렵네

일단 상하좌우로 K개의 칸을 이동할 수 있다.
이 말이 나는 만약 현재 칸이 'B' 이면 다른 이동하려는 두 칸이 'RE' 이면 이동할 수 있다. 인줄 알았지만,
다른 이동하려는 칸이 'R'이면 되는 것이다. 즉 뛰어 넘는다는 말이다.

    for i in range(4):
        temp_x, temp_y = x, y

        for _ in range(k):
            nx = temp_x + dx[i]
            ny = temp_y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if graph[nx][ny] == target[idx + 1]:
                    dp[x][y][idx] += dfs(nx, ny, idx + 1)
            temp_x, temp_y = nx, ny

temp_x, temp_y를 계속 업데이트 하며 움직이고,
graph[nx][ny] 와 target[idx+1]을 비교 한다.

그리고, dp를 이용해 현재 칸에 몇 번째 target[idx]를 찾으려는 것인지에 따른 DP를 만들어야 한다. 안 그래도 많은 메모리를 이용하기 때문에 DP를 이용해야 하고, 각 칸에 왔을 때 몇 번째 글짜를 가리키는지 나타내야 한다.

dp = [[[-1] * len(target) for i in range(m)] for i in range(n)]

3차원 리스트를 생각하는 것과, K 에서 좀 버거웠다.;;;

import sys

n, m, k = map(int, sys.stdin.readline().split())
graph = []
for i in range(n):
    graph.append(list(sys.stdin.readline().strip()))

target = list(sys.stdin.readline().strip())
dp = [[[-1] * len(target) for i in range(m)] for i in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]


def dfs(x, y, idx):
    if idx == len(target) - 1:
        dp[x][y][idx] = 1
        return dp[x][y][idx]
    if dp[x][y][idx] != -1:
        return dp[x][y][idx]

    dp[x][y][idx] = 0
    for i in range(4):
        temp_x, temp_y = x, y

        for _ in range(k):
            nx = temp_x + dx[i]
            ny = temp_y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if graph[nx][ny] == target[idx + 1]:
                    dp[x][y][idx] += dfs(nx, ny, idx + 1)
            temp_x, temp_y = nx, ny

    return dp[x][y][idx]


cnt = 0
for i in range(n):
    for j in range(m):
        if graph[i][j] == target[0]:
            cnt += dfs(i, j, 0)
print(cnt)