이번 문제는 다익스트라 알고리즘을 통해 해결하였다. 각 칸마다 가중치가 같았다면 BFS를 활용하여 구현했겠지만, 각 칸마다 가중치가 다르기 때문에 다익스트라를 활용하였다. 우선 테라와 출구의 좌표를 구하고, 두 위치의 값을 0으로 바꿔주었다(가중치가 0이기 때문에).

그리고 테라가 움직이는 함수를 먼저 구현하였다. 이 함수의 경우 주어진 방향으로 테라를 계속 이동시켜야 한다. 이때 범위를 벗어나거나, H를 만나면 테라는 더 이상 탈출이 불가하기 때문에 1e9를 반환해준다. R을 만나면 바위에 부딛혀 멈춘 것이므로 이전칸으로 한칸 이동시키고 이동을 멈추도록 해준다. 그리고 만약 현재 위치가 출구의 좌표와 같을 경우에도 이동을 멈춰준다. 이 과정에서 방문한 좌표의 가중치를 리스트에 담아주고, time 변수에 이 값들을 모두 더해 최종 좌표와 함께 반환해준다.

다익스트라 함수에서는 다익스트라 알고리즘을 활용하여 모든 좌표에 대한 최소 가중치를 구해준다. 이때 다음 좌표를 구하는 과정에서는 움직이는 함수를 사용하였다.

Code

import heapq
w, h = map(int, input().split())
grid = [list(str(input())) for _ in range(h)]
tera = []
exit = ()
for i in range(h):
    for j in range(w):
        if grid[i][j] == 'T':
            tera = [i, j]
            grid[i][j] = 0
        if grid[i][j] == 'E':
            exit = (i, j)
            grid[i][j] = 0
dy, dx = [0, 1, 0, -1], [1, 0, -1, 0]
def move(y, x, d):
    time = 0
    path = []
    while True:
        path.append(int(grid[y][x]))
        y, x = y+dy[d], x+dx[d]
        if not (0 <= y < h) or not (0 <= x < w) or grid[y][x] == 'H':
            return y, x, 1e9
        if grid[y][x] == 'R':
            y, x = y-dy[d], x-dx[d]
            break
        if (y, x) == exit:
            break
    time += (sum(path[1:]))
    return y, x, time
def dijkstra():
    q = []
    heapq.heappush(q, (0, tera[0], tera[1]))
    dist = [[1e9 for _ in range(w)] for _ in range(h)]
    dist[tera[0]][tera[1]] = 0
    while q:
        time, y, x = heapq.heappop(q)
        if time > dist[y][x]:
            continue
        for i in range(4):
            nxt_y, nxt_x, nxt_time = move(y, x, i)
            nxt_time += time
            if 0 <= nxt_y < h and 0 <= nxt_x < w and dist[nxt_y][nxt_x] > nxt_time:
                dist[nxt_y][nxt_x] = nxt_time
                heapq.heappush(q, (nxt_time, nxt_y, nxt_x))
    return dist[exit[0]][exit[1]]
answer = dijkstra()
if answer == 1e9:
    answer = -1
print(answer)