[백준-파이썬] 21772: 가희의 고구마 먹방

문제 보러 가기

아이디어, 배운 점 😍

맨 처음엔 가희의 위치를 찾아야 한다. 그리고 가희의 위치를 길로 만들었다.(그래서 갈 수 있도록~)
가희의 위치부터 탐색을 시작한다.

상하좌우를 탐색해서
범위 내이고

1. 장애물이면 못가니까 continue
2. 고구마이면 거기로 이동하되, 시간과 고구마 먹은 양을 1씩 증가
3. 길이면 거기로 이동하되, 시간만 1 증가했다.

시간이 다 되었을 때 먹은 고구마를 최대값으로 갱신한 후에 return을 해주었다.

---

처음에는 기계적으로..(?) visited 리스트를 만들어서 체크를 할까 했지만, 갔던 길을 또 갈 수 있으니까 체크할 필요가 없었다.

그 자리에 가만히 있을 수도 있다고 했지만 딱히 고려하진 않았다.
만약에 움직여서 고구마를 먹을 수 있으면, 고구마 먹는 게 이득이니까 움직여야 겠고!
움직여도 고구마 먹을 수 없다고 해도, 가만히 있든 움직이든 ate는 같으니까..

코드 ⭐

R, C, T = map(int, input().split())
arr = list(list(input()) for _ in range(R))

# 가희 위치 찾기
def find_G():
    for i in range(R):
        for j in range(C):
            if arr[i][j] == 'G':
                return (i, j)


i, j = find_G()
arr[i][j] = '.'  # 가희 위치 길로 만들기

# 상하좌우
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

# 탐색
max_ate = 0


def dfs(y, x, t, ate):
    global max_ate
    if t == T:  # 시간 다 되었으면
        max_ate = max(max_ate, ate)  # 최대값으로 갱신
        return

    for k in range(4):
        ny = y + directions[k][0]
        nx = x + directions[k][1]
        if 0 <= ny < R and 0 <= nx < C:  # 범위 내
            if arr[ny][nx] == '#':  # 장애물이면 갈 수 없음
                continue
            elif arr[ny][nx] == 'S':  # 고구마이면
                arr[ny][nx] = '.'  # 고구마 사라짐
                dfs(ny, nx, t + 1, ate + 1)
                arr[ny][nx] = 'S'  # 돌아오면 고구마 복구


            elif arr[ny][nx] == '.':  # 그냥 길이면 
                dfs(ny, nx, t + 1, ate)



dfs(i, j, 0, 0)
print(max_ate)