[BOJ] 백준 1520 내리막 길 (Python)

문제

1520번: 내리막 길

 

문제 해석

접근 방법

dfs와 dp를 함께 사용해 풀 수 있는 문제입니다.

 

dfs만 사용할 경우 (완전 탐색을 사용할 경우) M과 N이 최대 500이므로 시간 제한에 걸릴 수 있습니다.

이때, dp를 사용해 한 지점에서 목적지까지 갈 수 있는 경우의 수를 합산해서 저장한 후, 다음 지점의 경우의 수에 합산하는 것을 반복한다면 최초 한 번 방문한 지점에 대해서는 dfs를 실행하지 않아도 되므로 실행 시간을 줄일 수 있습니다.

 

전체 코드

from sys import stdin, setrecursionlimit
# M = 500, N = 500을 가정해 recursionlimit 설정
setrecursionlimit(250000)

M, N = map(int, stdin.readline().rstrip().split())
graph = [list(map(int, stdin.readline().rstrip().split())) for _ in range(M)]
dx, dy = [0, 0, 1, -1], [1, -1, 0, 0]

# 목적지까지 도착하는 경우의 수를 저장하는 2차원 배열
memo = [[-1]*N for _ in range(M)]

def dfs(x, y):
	# 목적지에 도달했으면 1 반환
    if (x, y) == (M-1, N-1):
        return 1
        
    # 방문한 적 있으면 dfs를 중단하고 해당 노드에 저장된 경우의 수 반환
    if memo[x][y] != -1:
        return memo[x][y]
        
    # 방문 처리
    memo[x][y] = 0

    for i in range(4):
        nx, ny = x+dx[i], y+dy[i]
        
        # 인접한 노드 중 현재 노드보다 높이가 낮은 노드에 저장된 경우의 수를 합산
        if 0 <= nx < M and 0 <= ny < N and graph[x][y] > graph[nx][ny]:
            memo[x][y] += dfs(nx, ny)
    
    return memo[x][y]

print(dfs(0, 0))

 

회고

이전에 풀었던 dp 문제들의 풀이를 그대로 적용하고자 했던 것이 걸림돌이 되었다. 결국 dp의 기본 원리는 이전에 계산한 값을 다음 계산에 어떻게 사용할 수 있을지 고민하는 것에서 출발한다는 것을 생각하자!

 

그리고 재귀 깊이 자체로는 시간 복잡도에 큰 영향을 주지 않는다는 것도 이번에 새롭게 알게 되었다. 재귀가 깊어지는 것을 피하려다가 오히려 실행 시간이 두 배 이상 늘어난 경험도 했다. 시간 복잡도를 논리적으로 생각하면서 푸는 습관을 가지자.

 

처음 작성한 코드

• 높이 내림차순으로 정렬 후, 높이 순서대로 경우의 수를 누적 계산한다 (dp)

from sys import stdin

M, N = map(int, stdin.readline().rstrip().split())
graph = []
for _ in range(M):
    graph += map(int, stdin.readline().rstrip().split())

idx_graph = []
for i, val in enumerate(graph):
    idx_graph.append((i, val))

memo = [0]*(M*N)
memo[0] = 1

idx_graph.sort(key=lambda x: x[1], reverse=True)


def check_idx(num):
    arr = [num+N, num-N]
    if num % N != 0:
        arr.append(num-1)
    if num % N != N-1:
        arr.append(num+1)
    return arr


for g in idx_graph:
    for i in check_idx(g[0]):
        if 0 <= i < M*N and graph[i] > graph[g[0]]:
            memo[g[0]] += memo[i]

print(memo[M*N-1])