백준: 17485 진우의 달 여행 (Large)

문제

17485번: 진우의 달 여행 (Large)

 

문제 풀이

 완전 탐색 + dp 문제이다. 탐색한 경로를 다시 탐색하지 않기 위해서는 메모이제이션을 통해, 각 공간을 지날 때 최솟값을 기록하고 이전의 값을 사용하는 방식을 사용하면 된다. 재귀로 풀면 문제는 어렵지 않게 풀 수 있으며 점화식은 다음과 같다.

dp[r][c][cur_dir] = min(dp[r][c][cur_dir], recursive_find(next_r, next_c), next_dir) + board[r][c])이며, 이를 통해, 최솟값을 반영하여 불필요한 탐색을 막을 수 있다.

 

코드

from sys import stdin, maxsize, setrecursionlimit


def visitable(loc, cur_dir, next_dir):
    r, c = loc
    return cur_dir != next_dir and 0 <= c < M


def solve(loc, cur_dir):
    r, c = loc
    #
    if r == N:
        return 0

    # 찾은 값이 있는 경우, 탐색할 필요 없음
    if dp[r][c][cur_dir] != maxsize:
        return dp[r][c][cur_dir]

    for next_dir, dc in enumerate(dirs):
        # r는 항상 1씩 증가, c는 3방향 (↙, ↓, ↘) 중 하나로 증감
        next_r, next_c = r + 1, c + dc
        if visitable((next_r, next_c), cur_dir, next_dir):
            dp[r][c][cur_dir] = min(dp[r][c][cur_dir], solve((next_r, next_c), next_dir) + board[r][c])

    return dp[r][c][cur_dir]


if __name__ == "__main__":
    # 사용하지 않으면 (RecursionError) 발생
    setrecursionlimit(2000)
    answer = maxsize
    N, M = map(int, stdin.readline().split())
    board = [list(map(int, stdin.readline().split())) for _ in range(N)]
    dp = [[[maxsize] * 3 for _ in range(M)] for _ in range(N)]

    # ↙, ↓, ↘
    dirs = (-1, 0, 1)

    answer = maxsize
    for i in range(M):
        for j in range(3):
            answer = min(answer, solve((0, i), j))

    print(answer)

 

 PyPy3로 제출하여야 시간초과가 발생되지 않으며, setrecursionlimit을 사용하지 않으면 런타임 에러가 발생한다.