[Coding Test] 가희의 고구마 먹방 (BAEKJOON: 21772번)

가희의 고구마 먹방

가희와 함께하는 1회 코딩 테스트의 2번 출제문제입니다. DFS와 Dynamic Programming을 이용해 푸는 문제였습니다.

잠시 Depth-First Search 방식의 장점을 알아보겠습니다.

• 탐색시 최대 깊이가 정해지기 때문에 최대 요구 메모리 공간을 명시할 수 있음
• 원본 배열의 값을 변이시켜도 함수가 종료되는 과정에서 원본 값을 복구할 수 있음

위의 장점을 잘 활용하면 Out of Memory를 피하며 코드를 구현할 수 있습니다. 실제로 저도 이번 SAMSUNG SW 역량테스트에서 Out of Memory를 이 방법으로 잡았습니다.

여러 함수를 실행하는 것 같아도 한 개의 논리적 과정을 거치며 이동합니다. 따라서 해당 함수가 반환되어 돌아온 뒤 다음 코드에 역과정을 넣으면 원본을 복구할 수 있습니다. 아래가 그 예시입니다. TURN, SP, MAP[ny][nx] 값은 한 줄기의 검색이 완료된 뒤 다시 모두 원본으로 복구됩니다.

        # increase sweet potato and turn
        SP += 1
        TURN += 1
        MAP[ny][nx] = '.'

        # do search
        CHK[TURN][ny][nx] = SP
        dfs(ny, nx)

        # return SP and TURN to original
        TURN -= 1
        SP -= 1
        MAP[ny][nx] = 'S'

저는 다음과 같은 과정을 통해 문제를 해결했습니다.

1. 가희의 시작 위치를 얻습니다.
2. 해당 칸에서 DFS 탐색 시작합니다.
3. 현재 칸에서 이동 가능한 다음 칸이 있을 때 3-1. 다음 칸에 고구마가 있다면
   • 턴을 하나 올리고, 고구마를 먹고, 먹은 개수를 높이고, 그 칸의 고구마를 지웁니다.
   • 이동합니다.
   • 턴을 하나 내리고, 고구마 먹은 개수를 하나 깎고, 그 칸에 다시 고구마를 나타냅니다.

   3-2. 다음 칸에 고구마가 없다면

   • 턴을 하나 올립니다.
   • 이동합니다.
   • 턴을 하나 내립니다.
4. 가희가 이동할 수 있는 최대 횟수가 됐을 때, 먹은 고구마 갯수가 기존 개수보다 많다면 업데이트합니다.

여기서 저는 속도를 조금 더 빨리하기 위해 DP[TURN][Y_IDX][X_IDX]를 선언했습니다. 각 턴에서 Y_IDX와 X_IDX에 해당하는 값은 특정 턴에 특정 위치에 도달했을 때의 최대로 먹은 고구마 개수입니다.

같은 횟수를 움직였는데 그 위치에서 먹은 고구마 수가 이미 더 많다면 이동을 굳이 확인하지 않도록 했습니다.

소스코드

from collections import deque

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

def dfs(y_idx, x_idx):
    global MAP, CHK, T, SP, TURN, answer, R, C

    if TURN == T:
        answer = max(SP, answer)
        return

    # search
    for i in range(4):
        nx = x_idx + dx[i]
        ny = y_idx + dy[i]

        # new x range check
        if not (0 <= nx < C):
            continue

        # new y range check
        if not (0 <= ny < R):
            continue

        # block check
        if MAP[ny][nx] == '#':
            continue

        if MAP[ny][nx] == 'S':
            # not a optimized path
            if SP + 1 < CHK[TURN + 1][ny][nx]:
                continue
            else:
                # increase sweet potato and turn
                SP += 1
                TURN += 1
                MAP[ny][nx] = '.'

                # do search
                CHK[TURN][ny][nx] = SP
                dfs(ny, nx)

                # return SP and TURN to original
                TURN -= 1
                SP -= 1
                MAP[ny][nx] = 'S'
        else:
            # not a optimized path
            if SP < CHK[TURN + 1][ny][nx]:
                continue
            else:
                # SP == CHK[TURN + 1][ny][nx] is dfs execution condition
                # increase sweet potato and turn
                TURN += 1

                # do search
                dfs(ny, nx)

                # return TURN to original
                TURN -= 1

def print_chk():
    global CHK, R, C, T

    for t in range(T+1):
        for i in range(R):
            print(*CHK[t][i])
        print()

if __name__=="__main__":
    R, C, T = map(int, input().split(' '))

    MAP = [list(input().strip()) for _ in range(R)]
    CHK = [[[0 for j in range(C)] for i in range(R)] for t in range(T + 1)]

    answer = 0

    for i in range(R):
        for j in range(C):
            if MAP[i][j] == 'G':
                SP, TURN = 0, 0
                dfs(i, j)
                break

    print(answer)