이번 문제는 다익스트라 알고리즘을 활용하여 해결하였다. 각 좌표에서 왼쪽으로 화살표를 왼쪽 비용이 k가 될때까지 돌리며 힙에 넣고, 오른쪽으로 화살표를 오른쪽 비용이 k가 될때까지 돌리며 힙에 넣고, 안돌리고 화살표대로 힙에 넣도록 하였다. 이때 넣기 전에는 비용 리스트를 확인하여 다음 방문 좌표에 대한 비용이 현재 계산된 비용보다 클 경우에만 넣도록 하였다. 그리고 최소힙을 제대로 활용하기 위해 힙에 들어가는 인자는 (max(l_cost, r_cost), l_cost, r_cost, y, x)로 넣어 주문서의 갯수가 가장 작은 것부터 꺼낼 수 있도록 하였다.

Code

import heapq
r, c, k = map(int, input().split())
grid = [list(str(input())) for _ in range(r)]
dy, dx = [-1, 0, 1, 0], [0, -1, 0, 1]
mapping = {'U': 0, 'L': 1, 'D': 2, 'R': 3}
def move():
    q = []
    heapq.heappush(q, (0, 0, 0, 0, 0))
    costs = [[1e9 for _ in range(c)] for _ in range(r)]
    costs[0][0] = 0
    while q:
        cost, l_cost, r_cost, y, x = heapq.heappop(q)
        if cost > costs[y][x]:
            continue
        if cost > k:
            continue
        l_cur = mapping[grid[y][x]]
        r_cur = mapping[grid[y][x]]
        tmp_l_cost = l_cost
        tmp_r_cost = r_cost
        while tmp_l_cost+1 <= k:
            l_cur = (l_cur+1)%4
            tmp_l_cost += 1
            ny, nx = y+dy[l_cur], x+dx[l_cur]
            if 0 <= ny < r and 0 <= nx < c:
                if costs[ny][nx] > max(tmp_l_cost, r_cost):
                    costs[ny][nx] = max(tmp_l_cost, r_cost)
                    heapq.heappush(q, (max(tmp_l_cost, r_cost), tmp_l_cost, r_cost, ny, nx))
        while tmp_r_cost+1 <= k:
            r_cur = (r_cur+3)%4
            tmp_r_cost += 1
            ny, nx = y + dy[r_cur], x + dx[r_cur]
            if 0 <= ny < r and 0 <= nx < c:
                if costs[ny][nx] > max(tmp_r_cost, l_cost):
                    costs[ny][nx] = max(tmp_r_cost, l_cost)
                    heapq.heappush(q, (max(tmp_r_cost, l_cost), l_cost, tmp_r_cost, ny, nx))
        ny, nx = y+dy[mapping[grid[y][x]]], x+dx[mapping[grid[y][x]]]
        if 0 <= ny < r and 0 <= nx < c:
            if costs[ny][nx] > cost:
                costs[ny][nx] = cost
                heapq.heappush(q, (cost, l_cost, r_cost, ny, nx))
    return costs
ans = move()
if ans[r-1][c-1] == 1e9:
    print('No')
else:
    print('Yes')