1. 문제풀이

최단 거리를 구하는 문제였기 때문에 BFS 로 접근했습니다. 우산을 통해서 왔던 길을 다시 돌아가야하는 경우도 고려해야하기 때문에, 단순히 방문표시보다는 현재 체력과 우산의 합산한 총 이동 가능 거리를 기준으로 판별해주었습니다.

따라서, 같은 지점이더라도 이동가능회수가 더 많은 경우 함께 탐색해주었습니다.

2. 정답코드

from collections import deque


def bfs(start):
    check = [[0]*N for _ in range(N)]  # 최대 이동가능 거리
    check[start[0]][start[1]] = H
    dq = deque([start])

    while dq:
        r, c, h, d, cnt = dq.popleft()
        for i in range(4):
            nr, nc = r + dr[i], c + dc[i]
            if 0 <= nr < N and 0 <= nc < N:
                if mp[nr][nc] == "E":
                    return cnt + 1

                nh, nd = h, d

                if mp[nr][nc] == "U":
                    nd = D

                if nd:
                    nd -= 1
                else:
                    nh -= 1

                if nh and nh+nd > check[nr][nc]: # 이동가능회수 기준 판별
                    check[nr][nc] = nh+nd
                    dq.append((nr, nc, nh, nd, cnt + 1))

    return -1


N, H, D = map(int, input().split())
dr = [0, -1, 0, 1]
dc = [1, 0, -1, 0]

mp = []

for i in range(N):
    lst = list(input())
    for j in range(N):
        if lst[j] == "S":
            start = (i, j, H, 0, 0)
            check[i][j] = H
    mp.append(lst)

print(bfs(start))