[파이썬] 백준 2186 : 문자판 (골드3)

[파이썬] 백준 2186 : 문자판 (골드3)

2186번: 문자판 (acmicpc.net)

---

문제

---

풀이

방향성 생각

• 내리막길이랑 비슷한 문제. 전형적인 DFS + DP
• 현재 노드를 결정하는데 3가지 요소가 있다.
• x,y좌표, 현재 몇 번째 단계인지. 3차원 DP로 작성한다.
• 중복 경로를 체크해줘야한다. 방문 안했으면 -1, 방문 했는데 도달하지 못하면 0, 도달 가능하면 1 이상의 숫자로 카운팅

 

전체코드

H,W,K = map(int,input().split())
arr = [list(input()) for _ in range(H)]
target = input()
L = len(target)

visit = [[[-1]*W for _ in range(H)] for _ in range(L)]
dire = [(1,0),(-1,0),(0,1),(0,-1)]

def dfs(x,y,l):
        
    if l == L:
        return 1
    
    if visit[l][y][x] != -1:
        return visit[l][y][x]
    
    count = 0
    for dx,dy in dire:
        for k in range(1,K+1):
            nx,ny = x+dx*k,y+dy*k
            if 0<=nx<W and 0<=ny<H and target[l] == arr[ny][nx]:
                count += dfs(nx,ny,l+1)
    visit[l][y][x] = count
    return visit[l][y][x]

answer = 0
for i in range(H):
    for j in range(W):
        if arr[i][j] == target[0]:
            answer += dfs(j,i,1)
print(answer)

 

코멘트

python3로 하면 41에서 터지는듯?