[ BOJ / Python ] 2186번 문자판

황승환·2022년 10월 5일
0

Python

목록 보기
490/498

이번 문제는 DP와 DFS를 활용하여 해결하였다. 우선 만들고자 하는 단어와 같은 좌표를 모두 start리스트에 저장하고, 3차원 리스트의 dp리스트를 만들었다. dp에는 해당 좌표와 해당 인덱스에서의 가짓수가 저장된다. DFS를 통해 탐색하며 dp리스트를 계속해서 갱신하고, 이를 통해 가짓수를 계속 더하여 값을 구하였다.

Code

n, m, k = map(int, input().split())
grid = [list(str(input())) for _ in range(n)]
word = list(str(input()))
dp = [[[-1 for _ in range(len(word))] for _ in range(m)] for _ in range(n)]
dy, dx = [0, 1, 0, -1], [1, 0, -1, 0]
start = []
answer = 0
for i in range(n):
    for j in range(m):
        if grid[i][j] == word[0]:
            start.append((i, j))
def dfs(y, x, idx):
    if idx == len(word):
        return 1
    if dp[y][x][idx] != -1:
        return dp[y][x][idx]
    dp[y][x][idx] = 0
    for i in range(4):
        for j in range(1, k+1):
            ny, nx = y+j*dy[i], x+j*dx[i]
            if 0 <= ny < n and 0 <= nx < m:
                if grid[ny][nx] == word[idx]:
                    dp[y][x][idx] += dfs(ny, nx, idx+1)
    return dp[y][x][idx]
for y, x in start:
    answer += dfs(y, x, 1)
print(answer)

업로드중..

profile
꾸준함을 꿈꾸는 SW 전공 학부생의 개발 일기

0개의 댓글