[Python] 2418번 단어 격자

 

 

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

---

 

24/11/14

 

 

예전에 북마크 해뒀다가 지금 해결한 문제다. 해결 방식은 어제 해결했던 내리막길 문제와 유사하다.

---

 

문제 접근 방식:

 

 

탑다운 DP로 접근했다.

 

DP상태는 다음과 같이 정의했다.

 

DP[i][j][k] = 지금까지 단어에서 k번째 글자까지 읽었고, (i, j)에 위치한 글자가 단어에서 k번째 글자일 때, 단어를 읽을 수 있는 방법의 수

 

이후, 모든 격자 칸을 조사하며, 이 격자 칸에 적힌 글자가 단어의 첫 글자와 일치한다면, 즉, (i, j)에 위치한 글자가 단어의 0번째 글자라면 DP[i][j][0] = 1로 초기화 해주었다.

 

이후 dfs를 통해 주변 8방향을 조사하며 구현했다.

 

우리가 원하는 값은 단어의 마지막 글자와 (i, j)에 위치한 글자가 일치할 때의 DP값들을 전부 더한 것이므로, 조건을 만족할 때 dfs를 돌렸다. 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 2418번 단어 격자
# DP
'''
접근 방법:
DP[i][j][k] = (i,j)에 위치한 글자가 k번째 글자일 때 단어를 읽을 수 있는 방법의 경우의 수
탑다운으로 해결해보자.
'''
import sys
input = sys.stdin.readline
sys.setrecursionlimit(500_000)

H, W, L = map(int, input().split())
G = [list(input().rstrip()) for _ in range(H)]
DP = dict()
dr, dc = [-1, -1, -1, 0, 0, 1, 1, 1], [-1, 0, 1, -1, 1, -1, 0, 1]
word = input().rstrip()
# DP값 초기화
for i in range(H):
    for j in range(W):
        if G[i][j] == word[0]:
            DP[(i, j, 0)] = 1
def dfs(i, j, k):
    if (i, j, k) in DP:
        return DP[(i, j, k)]
    A = 0
    if k == 0: return 0
    for t in range(8):
        ni, nj = i+dr[t], j+dc[t]
        if 0 <= ni < H and 0 <= nj < W and G[ni][nj] == word[k-1]:
            if (ni, nj, k-1) not in DP:
                dfs(ni, nj, k-1)
            A += DP[(ni, nj, k-1)]
    DP[(i, j, k)] = A
    return DP[(i, j, k)]
ans = 0
for i in range(H):
    for j in range(W):
        if G[i][j] == word[-1]:
            ans += dfs(i, j, L-1)
print(ans)