[PS] BOJ 21772 / 가희의 고구마 먹방

Minjun Kim

22 Oct 2025 • 2 min read

Thumbnail: Photo by muhammed [paqer (Unsplash)

문제 링크: https://www.acmicpc.net/problem/21772

백트래킹으로 고구마를 최대한 많이 먹어봅시다.

풀이

백트래킹

가희는 1개의 시작점에서 시작해, 주어진 격자 그래프를 탐색하며 $T$초 이내 ($1 \leq T \leq 10$)에 고구마를 최대한 많이 먹으려고 합니다. $T$가 작은 수 이므로, 백트래킹을 통해 가능한 경우를 모두 찾아서 최댓값을 구하면 됩니다.

유의할 점은, 가희는 이전에 방문했던 경로를 다시 방문해 다른 고구마를 먹을 수 있습니다. 따라서, 방문 여부를 기록하지 않고 백트래킹을 진행했습니다.

테스트 케이스

유용한 테스트 케이스를 몇 개 첨부합니다.

이전에 방문했던 경로를 다시 방문할 수 있음

# INPUT
3 3 6
GSS
S##
S#.
# ANSWER
4

# INPUT
5 5 10
##S##
##S##
SSG##
##S##
##S##
# ANSWER
6

가희가 시작 지점에서 움직이지 못할 수 있음

# INPUT
2 2 1
G#
#S
# ANSWER
0

전체 코드

input = open(0).readline

MOVE = ((1, 0), (0, 1), (-1, 0), (0, -1), (0, 0))
R, C, T = map(int, input().split())

room = [[""] * 100 for _ in range(100)]
start = None
for r in range(R):
    for c, tile in enumerate(input().rstrip()):
        if tile == "G":
            start = (r, c)
            tile = "."
        room[r][c] = tile

max_cnt = 0
def backtracking(time, cnt, r, c):
    if time == T:
        global max_cnt
        max_cnt = max(max_cnt, cnt)
        return

    for dr, dc in MOVE:
        nr = r + dr
        nc = c + dc
        if 0 <= nr < R and 0 <= nc < C:
            if room[nr][nc] == "S":
                room[nr][nc] = "."
                backtracking(time + 1, cnt + 1, nr, nc)
                room[nr][nc] = "S"
            elif room[nr][nc] == ".":
                backtracking(time + 1, cnt, nr, nc)

backtracking(0, 0, *start)
print(max_cnt)

solution.py