백준 2186 문자판 (파이썬)

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

2186번: 문자판

dfs + 메모이제이션로 구현하면 된다

 

1. word에 문자열을 단어로 나눠서 저장하고 start에 시작점이 될 후보를 저장한다

2. start에 있는 좌표를 하나씩 불러와서 dfs를 실행한다

3. idx를 증가시키면서 word 순서대로 이동할 수 있는지 확인한다

4. idx가 word 리스트 길이와 같으면 문자열을 완성했으므로 1을 return하여 가능한 경우의 수를 증가시킨다

import sys

input = sys.stdin.readline
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

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

    c[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 a[nx][ny] == word[idx]:
                    c[x][y][idx] += dfs(nx, ny, idx+1)
            temp_x, temp_y = nx, ny
    return c[x][y][idx]

n, m, k = map(int, input().split())
a = []
for _ in range(n):
    a.append(list(input().strip()))
word = list(input().strip())

start = []
for i in range(n):
    for j in range(m):
        if a[i][j] == word[0]:
            start.append([i, j])

ans =  0
c = [[[-1] * len(word) for _ in range(m)] for _ in range(n)]
for i in range(len(start)):
    x, y = start[i]
    ans += dfs(x, y, 1)
print(ans)