문제

가희는 고구마를 정말 좋아합니다.

이번에도 어김 없이 고구마 냄새가 났는데, 고구마가 보이지 않습니다. 오빠가 방 안에 고구마를 숨겨 놓았기 때문입니다.

오빠는 가희에게 하나의 게임을 제안하고, 게임의 규칙을 설명해 주었습니다. 게임 규칙은 아래와 같습니다.

가희는 1초마다 상하좌우 방향 중 한 방향으로 1번 이동하거나, 이동하지 않고 그 자리에 머무를 수 있습니다.
가희가 이동한 지점에 고구마가 있는 경우에는, 고구마를 먹습니다. 고구마를 먹는 데 걸리는 시간은 없다고 가정합니다.
가희가 고구마를 먹으면, 고구마가 다시 그 자리에 생기지 않습니다.
가희는 현재 위치에서 T초만큼 이동했을 때 고구마를 최대한 많이 먹고 싶습니다. 가희가 최대 몇 개의 고구마를 먹을 수 있는지 알려주세요.

입력

첫 번째 줄에 맵의 세로 크기 R, 가로 크기 C, 가희가 이동하는 시간 T가 주어집니다.

두 번째 줄부터 R+1번째 줄까지 길이가 C인 문자열이 주어집니다.

주어지는 문자열에 있는 문자는 가희를 나타내는 'G', 고구마를 나타내는 'S', 빈 칸을 나타내는 '.', 장애물을 나타내는 '#' 중 하나 입니다.

출력

문제에 대한 답을 출력합니다.

제한

2 ≤ R ≤ 100
2 ≤ C ≤ 100
1 ≤ T ≤ 10
가희를 나타내는 문자인 'G'는 맵 안에 하나만 있습니다. 'G'가 있는 위치는, 가희의 현재 위치입니다.
'S'가 있는 위치에 고구마는 1개 있습니다.
고구마와 장애물은 최소 1개 이상 있습니다.
가희는 장애물을 뛰어 넘거나 통과할 수 없습니다.
가희는 맵 밖으로 나갈 수 없습니다.

풀이

간단한 미로찾기 로직과 비슷하다 . 조금씩 꼬아 낸 문제
1) 입력받기 ....#..S.. 이런 식으로 입력을 받은 걸 리스트로 띄워 받아야 했다.
2) 먹은 곳을 돌아갈 수 있다는 조건이 어려웠다. dfs 안에 변수로 visited 를 받아 새로 초기화된 visited도 넣을 수 있게 만들었다.
3) count가 안끝나면 result가 비어있게 된다 -> 처리해주기

↓고구마를 먹는 순간 visit 초기화해서 다시 돌아갈 수 있게 만들기

import sys
sys.stdin = open('input.txt')
input = sys.stdin.readline

R,C,T = map(int,input().split()) # 입력받기
graph =[]
for _ in range(R):
    ls =[]              # 한 글 자 씩 받 는 법
    ls.extend(input())
    if '\n' in ls:      # 마지막에 띄워쓰기가 있다면
        ls.remove('\n') # 지워주고
    graph.append(ls)    # 그 리스트를 넣어준다

gahee = [0,0]           # 가희가 있는 곳
for i in range(R):
    for j in range(C):
        if graph[i][j]=='G':
            graph[i][j]='.'     # 찾아서 빈 곳으로 만들어 주고
            gahee = [i,j]       # 위치를 저장한다.


visit = [[0]*C for _ in range(R)]   # 방문 처리용
visit[gahee[0]][gahee[1]] = 1       # 가희를 방문처리 먼저 해주기

result = []                     # 결과 창 
def dfs(y,x,time,potato,visit): # dfs 를 돌면서 (내위치,남은기회,먹은개수,방문유무확인용)
    if time == 0:               # 갈수있는 기회가 없다면
        result.append(potato)   # 먹은개수를 결과에 넣는다
        return                  
    dy = [0,0,1,-1]             # 네방향 순회하면서
    dx = [1,-1,0,0]
    for i in range(4):
        ny,nx = dy[i]+y , dx[i]+x
        if 0<=ny<R and 0<=nx<C: # 범위내에있고
            
            if graph[ny][nx]=='.' and visit[ny][nx]==0: # 길이 열려있고 방문 안했다?
                visit[ny][nx]=1     # 방문 시키고
                dfs(ny,nx,time-1,potato,visit)  # dfs 순회를 하는데
                visit[ny][nx]=0     # 순회가 끝나면 방문처리철회

            if graph[ny][nx]=='S' and visit[ny][nx]==0: # 고구마라면?
                graph[ny][nx]='.'   # 먹었다! 먹은자리 비우기
                
                newvisit = [[0]*C for _ in range(R)]    # 중요한 로직
                # 고구마를 먹고나면 모든 방문 처리를 다 없애서 다시 돌아갈 수 있도록 만들기
                dfs(ny,nx,time-1,potato+1,newvisit) # 새로운 visit를 넣어준다
                graph[ny][nx]='S'   # 고구마 다시 생기기


dfs(gahee[0],gahee[1],T,0,visit)
if len(result)==0:      # 이거 때문에 valueerror 났었음
    print(0)            # count가 남았는데 끝나면 result가 비게된다.
else:
    print(max(result))  # 최고값 구해주기
    ```