이번 문제는 다이나믹 프로그래밍과 DFP를 이용하여 해결하였다. 미로의 범위 내에서 순환하는 좌표와 순환하지 않고 범위를 벗어나는 좌표를 찾아내는 문제로, dp리스트에 순환 여부를 저장하고, DFS를 통해 순회하며 만약 다음 dp가 순환하거나 순환하지 않는다면 현재 dp를 다음 dp와 같은 값으로 갱신해주는 방식으로 하여 해결하였다.

Code

import sys
sys.setrecursionlimit(10**6)
n, m = map(int, input().split())
grid = [list(str(input())) for _ in range(n)]
dp = [[0 for _ in range(m)] for _ in range(n)]
dy, dx = [0, 1, 0, -1], [1, 0, -1, 0]
mapping = {'R': 0, 'D': 1, 'L': 2, 'U': 3}
def find_dest(y, x):
    global answer
    d = mapping[grid[y][x]]
    ny, nx = y+dy[d], x+dx[d]
    if 0 <= ny < n and 0 <= nx < m:
        if not dp[ny][nx]:
            dp[y][x] = -1
            dp[y][x] = find_dest(ny, nx)
        else:
            dp[y][x] = dp[ny][nx]
        return dp[y][x]
    return 1
answer = 0
for i in range(n):
    for j in range(m):
        if not dp[i][j]:
            dp[i][j] = -1
            dp[i][j] = find_dest(i, j)
        if dp[i][j] == 1:
            answer += 1
print(answer)