[BOJ][🟡5][백준#21772] 가희의 고구마 먹방

문제 출처

BAEKJOON Online Judge #21772

문제

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

이번에도 어김 없이 고구마 냄새가 났는데, 고구마가 보이지 않습니다. 오빠가 방 안에 고구마를 숨겨 놓았기 때문입니다. 오빠는 가희에게 하나의 게임을 제안하고, 게임의 규칙을 설명해 주었습니다. 게임 규칙은 아래와 같습니다.

가희는 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

입력

11 11 5
........G..
......S.#S.
........#.S
...........
...........
.##########
.##########
...........
...........
##########.
...........

출력

2

예제 2

입력

11 11 5
G....S.....
...........
...........
...........
...........
...........
.....#.....
...........
...........
...........
...........

출력

1

My Sol

def main():
    def find_G():
        for i in range(I):
            for j in range(J):
                if mat[i][j] == 'G':
                    return i, j

    def dfs(i, j, move, cnt, ate):
        if move == T:
            return cnt

        cur_max = 0
        for di, dj in ((-1, 0), (1, 0), (0, 1), (0, -1)):
            si, sj = i + di, j + dj
            if not (0 <= si < I and 0 <= sj < J): continue
            if mat[si][sj] == '#': continue

            new_ate = set([*ate])
            new_cnt = cnt
            if mat[si][sj] == 'S':
                if not (si, sj) in ate:
                    new_ate.add((si, sj))
                    new_cnt += 1
                dfs_max = dfs(si, sj, move + 1, new_cnt, new_ate)
            else:
                dfs_max = dfs(si, sj, move + 1, cnt, new_ate)
            cur_max = max(cur_max, dfs_max)

        return cur_max

    I, J, T = map(int, input().split())
    mat = [list(input()) for _ in range(I)]
    gi, gj = find_G()
    ret = dfs(gi, gj, 0, 0, set())
    return ret

print(main())

dfs를 이용해서 해결할 수 있는 문제였다. 단순한 bfs, dfs를 사용하는 것이 아니라, 이전에 고구마를 지나쳤는지 확인해야하므로, 모든 움직일 수 있는 경우의 수를 모두 고려해 문제를 해결했다.

1. 입력을 받는다.
2. 가희(G)의 위치를 확인해 시작 좌표를 확인한다. 나는 이를 find_G 라는 함수를 작성해 찾아냈다.
3. dfs라는 함수로 모든 움직을 확인하는데, 이는 재귀함수로 move가 T가 되는 시점이 종료 조건이다. 해당 경로까지 저장된 고구마의 개수를 반환한다.
4. dfs 함수는 인자로 들어온 좌표의 상하좌우를 조회하여 맵을 벗어나거나 장애물인 경우를 제외하고 이동한다.
5. 지금까지의 경로에서 먹은 고구마의 좌표들을 ate set으로 받는데, 깊은 복사를 위해서 spread 한 뒤 다시 set에 넣어 새로운 set으로 만들어준다.
6. 만약 이동하려는 좌표가 ‘S’가 아니라면 그냥 move를 1 늘리는 무의미한 이동이므로 인자를 조정해 dfs함수를 실행하면 된다.
7. 만약 이동하려는 좌표가 ‘S’라면, 고구마를 발견한 상황인데, 이때 ate 에 목표 좌표가 있다면 이미 방문한 것이므로 그냥 이동한다. 하지만 만약 ate에 이동 좌표가 없다면 고구마를 새로 하나 먹은 것이므로 new_cnt를 1 늘리고 ate에 이동 좌표를 넣어 인자로 전달한다. 이후엔 ate에 해당 좌표가 있으므로 중복 카운트 되는 일이 없을 것이다.
8. 이렇게 사방으로 이동하는 모든 경우의 dfs 함수 반환값 중 가장 큰 값을 따져 반환하면, main 함수에서 최초로 호출한 dfs의 반환값은 T번 이동한 경우 얻을 수 있는 고구마의 최대개수가 된다.
9. 이를 출력한다.

결과

맞았습니다!!

모범답안

출처

def recur(r, c, t, eat):
    global ans
    if eat + t <= ans:
        return
    if t == 0:
        if eat > ans:
            ans = eat
        return
    for d in range(4):
        nr, nc = r + dr[d], c + dc[d]
        if 0 <= nr < R and 0 <= nc < C and arr[nr][nc] != '#':
            if arr[nr][nc] == 'S':
                arr[nr][nc] = '.'
                recur(nr, nc, t-1, eat+1)
                arr[nr][nc] = 'S'
            else:
                recur(nr, nc, t-1, eat)

R, C, T = map(int, input().split())
arr = []
TF = False
for i in range(R):
    arr.append(list(input()))
    if not TF and 'G' in arr[i]:
        TF = True
        sr, sc = i, arr[i].index('G')
dr = [0, 1, 0, -1]
dc = [1, 0, -1, 0]
ans = 0
recur(sr, sc, T, 0)
print(ans)

가장 연산시간이 짧은 코드를 분석해보려 한다. 이 경우 똑같이 DFS를 사용하기는 했지만, 남은 움직임의 기회와 현재 먹은 고구마의 개수의 합이 현재까지의 최대 고구마양 보다 적거나 같다면 더 진행하는 의미가 없으므로 중단하는 백트래킹을 사용하였다.

무엇보다 돋보이는 것은 고구마의 중복 체크를 방지하기 위해 고구마의 좌표를 밟으면 ‘S’를 ‘.’로 변경하고 해당 dfs를 모두 진행하여 고구마의 최댓값에 대한 계산을 마치고 돌아오면 ‘.’를 다시 ‘S’로 바꾸는 방식을 활용한 것이다. 내가 별개의 메모리 공간을 가지는 set을 수없이 만들어 인자로 넘긴 방식보다 훨씬 효율적인 방식이었다.