[백준] 내리막 길

https://www.acmicpc.net/problem/1520

1520번: 내리막 길

DFS와 다이나믹 프로그래밍을 사용하는 문제입니다. 

 

문제부터 간단하게 요약하면, 

다음과 같이 2d array에서 각 숫자들은 높이를 의미합니다. 가장 왼쪽 위에서 가장 오른쪽 밑으로 도달하는 경로의 수를 구해야 하는데, 이 때, 높이가 높은 곳에서 낮은 곳으로 이동하는 경우의 수를 return 해야 합니다. 

 

<Solution>

.우선 아이디어는 다음과 같습니다. 특정 칸에 도착을 했다고 가정해봅시다. 이 때, 그 이후에 도착지점으로 가는 경우의 수는 그 칸에서 도착지점으로 가는 경우의 수와 같습니다. 

 

따라서 (a,b) 라는 칸에서 도착지점으로 가는 경우의 수는 4방향으로 이동하는 경우를 체크해서[(a-1,b), (a,b-1), (a+1,b), (a,b+1)], 만약 이동이 가능할 시, 그 칸에서부터 도착지점까지 갈 수 있는 경우의 수를 를 더해서 업데이트 시켜주어야 합니다. 이 때, 만약 그 칸이 이전에 조회된 적이 있다면, dfs를 돌지않고 바로 메모리에서 가져옵니다. 

실제 구현은 아래와 같습니다.

import sys
sys.setrecursionlimit(10**6)
m , n = map(int,sys.stdin.readline().rstrip().split())

# build 2d array
array = [list(map(int,sys.stdin.readline().rstrip().split())) for _ in range(m)]

# print(array)

# right down up left
d_row = [0, 1, 0, -1]
d_column = [1, 0, -1, 0]

dp = [[0]* n for _ in range(m)]
visited = [[False]*n for _ in range(m)]

def outofblock(row_size,column_size, row_index, column_index): # num row, num column index index
    return row_index<0 or row_index>row_size-1 or column_index<0 or column_index>column_size-1

def search(row,column):
    # if end
    if row == m-1 and column == n-1:
        return 1
    # if already visited
    if visited[row][column]:
        return dp[row][column]
    else:
        visited[row][column] = True
        tmp = 0
        # move
        for i in range(4):
            new_row = row + d_row[i]
            new_column = column + d_column[i]
            if not outofblock(m, n, new_row, new_column) and array[row][column]>array[new_row][new_column]:
                tmp += search(new_row,new_column)
        dp[row][column] = tmp
        return tmp

print(search(0,0))