[Python] 21772번 가희의 고구마 먹방

https://www.acmicpc.net/problem/21772

---

 

24/05/14

 

 

업다운 랜디를 하다가 만난 문제이다. 처음에는 BFS로 접근할까 하다가 DFS로 방향을 틀어 접근했다.

---

 

문제 접근 방식:

 

 

BFS로 접근할 수도 있다. 그 이유는 최대 10번을 탐색하고 한 번 할 때 4방향을 탐색하기 때문에 $4^{10}$번만 탐색하면 충분하고, 이는 시간 안에 들어오기에 충분하기 때문이다.

 

하지만 DFS로 접근하는 것이 더 쉬울 것 같아서 DFS로 접근했다.

 

무의식 중에 재귀 깊이를 10만으로 늘린 코드를 작성하긴 했지만, 사실은 10번만 탐색하기 때문에 그렇게까지 깊게 늘리지 않아도 되었던 것 같기도 하다.

 

DFS를 진행하는데, 들어간 자리에 고구마가 있으면 고구마를 먹었다는 표시로, 고구마 글자를 빈 글자로 교체해주었다.

 

이후 되돌아갈때는 다시 고구마 글자를 되돌려 놓음으로써 돌아갔다는 표시를 해주었다.

 

그냥 백트래킹 진행한 것이다.

 

최대로 먹었던 고구마는 MAX_goguma라는 변수를 전역변수로 사용하여 구해주었다. 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 21772번 가희의 고구마 먹방
# DFS
'''
접근 방법:
DFS
'''
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100_000)

R, C, T = map(int, input().split())
G = [list(input().rstrip()) for _ in range(R)]
sr, sc = 0, 0
flag = False
for i in range(R):
    for j in range(C):
        if G[i][j] == 'G':
            sr, sc = i, j
            flag = True
            break
    if flag: break
dr, dc = [-1, 1, 0, 0], [0, 0, -1, 1]
MAX_goguma = 0
def dfs(row, col, time, goguma):
    global MAX_goguma
    if time == T:
        if MAX_goguma < goguma:
            MAX_goguma = goguma
        return
    for i in range(4):
        nr, nc = row+dr[i], col+dc[i]
        if 0 <= nr < R and 0 <= nc < C and G[nr][nc] != '#':
            if G[nr][nc] == 'S':
                G[nr][nc] = '.'
                dfs(nr, nc, time+1, goguma+1)
                G[nr][nc] = 'S'
            else:
                dfs(nr, nc, time+1, goguma)
    return

dfs(sr, sc, 0, 0)
print(MAX_goguma)