[Backjoon] 1520 내리막 길 Python 문제 풀이

출처 : 내리막 길

문제해석

• 입력받은 맵을 (0,0)좌표에서 DFS탐색을 시작한다.

• 4방탐색을 통해 다음에 이동할 좌표의 인덱스가 경계를 벗어나지 않으면서 현재좌표값보다 높이가 더 낮을때만 dfs 함수를 재귀 호출한다.

• 최종적으로 (n-1,m-1)좌표에 도달했을때마다 ans값을 1씩 더해준다.

• 모든 dfs 탐색이 끝난 이후 최종적으로 나온 ans값을 출력한다.

처음엔 여기까지 해서 풀어본 결과 시간초과가 나왔다.

(0,0)에서 시작해 dfs로 가능한 곳을 모두 탐색하였기에 너무 많은 경우의 수가 있기때문에 시간초과라는 결과가 나왔다.

따라서 시간초과를 줄이기 위한 핵심은 DFS에 DP 방식을 결합하는 것이다.

isVisited 리스트에 -1, 0, n으로 구분하여 각각 미방문,방문한경우,경로완성수로 구분해준다.

1. 미방문(-1)에 대하여 조건을 만족하는 좌표(현재좌표보다 작은 값)으로 이동하며 이동(방문)하였다는 의미로 0으로 초기화해준다.
2. 목표지점(n-1,m-1)에 도달하면 시작점에서 도착점까지 성공적으로 방문한 한 가지 경로가 되므로 1을 반환해주고, 해당 값을 지금까지 이동해온 경로 내의 모든 리스트 값에 더해준다.
3. 만약에 현재 방문중인 경로를 이미 다른 경로에서 방문하여 -1이 아닌 다른 값으로 갱신되어져 있다면(0 or n) 더 이상의 탐색은 진행하지 않고 해당 값을 반환해준다.(만약 현재 방문한 좌표가 0이라고 한다면, 해당 좌표를 경로로 그 어떤 경우에도 목표지점으로 도달할 수 없다는 뜻이고, n이라면 해당 좌표를 통해 목표지점으로 가는 경우의 수를 지금까지 n개를 찾았다는 것이다.)

이런식으로 이미 완성된 경로의 수를 방문한 좌표에서 총 몇개인지를 굳이 탐색을 끝까지 하지 않고 바로 반환해주므로써 수행시간을 줄일 수 있다.

해답코드

실패한 코드(시간초과)

#내리막 길
import sys
sys.setrecursionlimit(10 ** 9)

input = sys.stdin.readline

n,m = map(int,input().split())
maps = [[0] * m for _ in range(n)]
isVisited = [[False]*m for _ in range(n)]
for y in range(n):
    maps[y] = list(map(int,input().split()))

ans=0

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


def dfs(startY,startX):
    global ans
    if startY==n-1 and startX==m-1:
        ans += 1
    for d in range(4):
        ny, nx = startY+dy[d], startX+dx[d]
        if 0<=ny<n and 0<=nx<m and maps[startY][startX]>maps[ny][nx] and not isVisited[ny][nx]:
            isVisited[ny][nx]=True
            dfs(ny,nx)
            isVisited[ny][nx]=False

dfs(0,0)
print(ans)

DFS+DP(정답코드)

#내리막 길
import sys
sys.setrecursionlimit(10 ** 9)

input = sys.stdin.readline

n,m = map(int,input().split())
maps = [list(map(int,input().split())) for _ in range(n)]
isVisited = [[-1]*m for _ in range(n)]

ans=0

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

def dfs(startY,startX):
    #목적지 도착시 해당경로 내 모든 배열값 추가
    if startY==n-1 and startX==m-1:
        return 1
    #이미 방문한 곳이면 해당 좌표에서 도착 가능한 모든 경로의 수 추가
    if isVisited[startY][startX] != -1:
        return isVisited[startY][startX]

    #방문하지 않은 곳이면 방문했지만 아직 경로완성을 찾지 못했다는 의미로 0으로 초기화
    isVisited[startY][startX]=0

    #4방탐색
    for d in range(4):
        ny, nx = startY+dy[d], startX+dx[d]
        if 0<=ny<n and 0<=nx<m and maps[startY][startX]>maps[ny][nx]:
            isVisited[startY][startX] += dfs(ny,nx)

    return isVisited[startY][startX]
print(dfs(0,0))