이번 문제는 BFS를 통해 해결하였다. 처음에는 모든 경우를 확인한다고 생각하여 백트레킹으로 구현하였다. 시작점을 찾고, 백트레킹을 통해 좌표들을 탐색하며 방문처리를 하고, U에 도달했을 때 현재 우산의 내구도를 d로 갱신해주도록 하였다. 그리고 다음 좌표값이 E일 경우에 바로 종료하도록 하였다.

그러나 시간초과가 발생하였고, BFS를 통해 해결하면 해결될 것이라는 생각을 하였다. 그래서 같은 방식으로 BFS로 구현하였고, 많은 시도 끝에 해결할 수 있었다.

Code

처음 코드 (Backtracking, 시간초과)

import sys
sys.setrecursionlimit(10**6)
n, h, d = map(int, input().split())
grid = [list(str(input())) for _ in range(n)]
sy, sx = 0, 0
for i in range(n):
    for j in range(n):
        if grid[i][j] == 'S':
            sy, sx = i, j
dy, dx = [0, 1, 0, -1], [1, 0, -1, 0]
visited = [[0 for _ in range(n)] for _ in range(n)]
visited[sy][sx] = h
answer = 1e9
def to_safe(y, x, cur_h, cur_d, cnt):
    global answer
    if answer < 1e9:
        return
    if cur_h == 0:
        return
    for i in range(4):
        ny, nx = y+dy[i], x+dx[i]
        if 0 <= ny < n and 0 <= nx < n and not visited[ny][nx]:
            if grid[ny][nx] == 'E':
                answer = cnt+1
                return
            nxt_h, nxt_d = cur_h, cur_d
            if grid[ny][nx] == 'U':
                nxt_d = d
            if nxt_d:
                nxt_d -= 1
            else:
                nxt_h -= 1
            if not nxt_h:
                return
            if visited[ny][nx] < nxt_h:
                tmp = visited[ny][nx]
                visited[ny][nx] = nxt_h
                to_safe(ny, nx, nxt_h, nxt_d, cnt+1)
                visited[ny][nx] = tmp
to_safe(sy, sx, h, 0, 0)
if answer == 1e9:
    answer = -1
print(answer)

정답 코드 (BFS)

from collections import deque
n, h, d = map(int, input().split())
grid = [list(str(input())) for _ in range(n)]
sy, sx = 0, 0
for i in range(n):
    for j in range(n):
        if grid[i][j] == 'S':
            sy, sx = i, j
dy, dx = [0, 1, 0, -1], [1, 0, -1, 0]
visited = [[0 for _ in range(n)] for _ in range(n)]
def to_safety_zone():
    q = deque()
    q.append((sy, sx, h, 0, 0))
    visited[sy][sx] = h
    while q:
        y, x, cur_h, cur_d, cnt = q.popleft()
        for i in range(4):
            ny, nx = y + dy[i], x + dx[i]
            if 0 <= ny < n and 0 <= nx < n:
                if grid[ny][nx] == 'E':
                    return cnt+1
                nxt_h, nxt_d = cur_h, cur_d
                if grid[ny][nx] == 'U':
                    nxt_d = d
                if nxt_d:
                    nxt_d -= 1
                else:
                    nxt_h -= 1
                if not nxt_h:
                    continue
                if visited[ny][nx] < nxt_h:
                    visited[ny][nx] = nxt_h
                    q.append((ny, nx, nxt_h, nxt_d, cnt+1))
    return -1
print(to_safety_zone())