문제: 1520번: 내리막 길 (acmicpc.net)


최근 제출하고 TLE 먹은 코드: http://boj.kr/57b2fad690bc4939a4555e68dd0eefeb

(아래 코드는 주석만 제거한 동일 코드입니다.)


import sys

input = sys.stdin.readline

n, m = map(int, input().split(' '))

board = []
for _ in range(n):
    board.append(list(map(int, input().split(' '))))

dp = [[0 for _ in range(m)] for _ in range(n)]
dp[n - 1][m - 1] = 1
def func(r, c):
    if(dp[r][c] != 0):
        return dp[r][c]
   
    value = 0
    nr = [r - 1, r + 1, r, r]
    nc = [c, c, c - 1, c + 1]

    for i in range(4):
        if(nr[i] < 0 or nr[i] >= n or nc[i] < 0 or nc[i] >= m):
            continue

        if(board[r][c] > board[nr[i]][nc[i]]):
            value += func(nr[i], nc[i])
    dp[r][c] = value
    return dp[r][c]
   

print(func(0, 0))


문제 조건상 한 지점에서 다른 지점으로 움직일 때에는 방향이 정해져 있기 때문에

처음에는 visited 배열을 사용하지 않는 BFS로 풀었다가 16% 쯤에서 TLE를 먹었습니다.


그래서 뭐가 문제일까 하다가 위의 방식대로 하면 이미 가본 적이 있는 경로 또한 다시 탐색해서 시간 초과가 날 수 있다고 생각했고,


그러면 가본 적이 있는 경로는 탐색하지 않도록 dp를 사용하면 되겠다해서 위처럼 코드를 수정한 뒤 제출했으나....


33%에서 TLE를 먹었습니다. (C++로 제출해도 TLE인 것을 보니 풀이가 잘못된 것은 맞는 것 같습니다.)


붙들어둔 시간이 꽤 되어서 힌트를 조금 얻고 싶은데, 혹시나 신경 쓰이는 부분이나 조금 더 공부하면 좋겠다 싶은 내용이 있으면 댓글로 남겨주시면 감사하겠습니다.


늘 감사합니다.