백준 30689. 미로 보수

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

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def dfs(y,x):
    global ans

    visited[y][x] = 1 # 방문처리

    dy, dx = direction_map[arr[py][px]]
    ny, nx = y+dy, x+dx

    if nx < 0 or ny < 0 or nx >= m or ny >= n: # 이동했을 때 탈출할 수 있으면
        done[y][x] = 1
        return

    if done[ny][nx]: # 중복계산방지
        done[y][x] = 1
        return

    elif visited[ny][nx]: # 이동하면 방문했던 곳일 경우
        sy, sx = ny, nx
        min_cost_in_cycle = float('inf')
        while True: # 사이클 한번을 돌면서 최솟값을 찾아 갱신
            min_cost_in_cycle = min(min_cost_in_cycle, cost[sy][sx])
            dy, dx = direction_map[arr[sy][sx]]
            sy += dy
            sx += dx
            if (sy, sx) == (ny, nx):
                break
        ans += min_cost_in_cycle

    else: # 계산도 안됐고, 방문하지도 않았을 경우
        dfs(ny, nx)

    done[y][x] = 1


n, m = map(int,input().split())
arr = [list(input().rstrip()) for _ in range(n)]
cost = [list(map(int,input().split())) for _ in range(n)]
visited = [[0] * M for _ in range(N)]
done = [[0] * M for _ in range(N)]
direction_map = {'D': (1, 0), 'U': (-1, 0), 'R': (0, 1), 'L': (0, -1)}
ans = 0

for j in range(n):
    for i in range(m):
        dfs(j,i)

print(ans)

done 테이블 이용하는 부분이랑 사이클 돌면서 최솟값 갱신하는 부분이 어렵다...