[백준 1520번] 내리막길 (+DP 개념)

DFS, BFS 알고리즘 개념을 공부해보겠습니다.

 

특히, 이번 문제에서는 DP(Dynamic programming)의 개념이 추가되었습니다.

 

DP란 '동적 계획법'이란?

일반 재귀함수에서의 불필요한 반복을 없애고 효율을 높이기 위해 이전 값(반복 값)을 저장해서 계산 효율화를 증대시킨 알고리즘입니다.

 

DP 적용 상황

① Overlapping subproblems (겹치는 부분 문제)

② Optimal Substructure (최적 부분 구조)

이번 내리막길 문제에서는 ①에 해당되는 상황이 발생하여 DP를 적용해보려 합니다.

 

DP 구현방식

① Bottom-up (반복문 방식, Tabulation)

 : 첫 시작 값부터 저장시켜 필요할 때마다 반복적으로 불러온다.

② Top-down (재귀함수 방식, Memoization)

 : 가장 최근 값을 불러온다.

 

Memoization (메모화)

DP알고리즘의 핵심 방법으로 한번 계산한 값을 저장하고 다시 사용하는 과정으로 메모한다고 표현하다.

보통 메모를 위해 '배열'의 형태의 데이터를 활용한다.

 

 

첫 답안의 경우 DP 개념을 모르고, DFS 알고리즘으로만 접근해서 문제를 풀었습니다.

하지만, recursionerror 메시지가 발생해서 DP 개념을 찾아보게 되었습니다.

 

[이전 답안]

import sys

sys.stdin = open('input.txt', 'r')

M, N = map(int, input().split())
graph = [[] for i in range(M)]
visited = [[0]*N for i in range(M)]
dx = [0,0,1,-1]
dy = [-1,1,0,0]
result = []

for i in range(M):
    graph[i] = list(map(int, input().split()))

def dfs(x, y):
    num = 0
    visited[x][y] = 1
    for i in range(4):
        # print(x,y,x+dx[i],y+dy[i])
        if (x + dx[i] >= 0) and (y + dy[i]) >= 0 and (x + dx[i]) < M and (y + dy[i]) < N:
            # print(graph[x][y], graph[x+dx[i]][y+dy[i]])
            if graph[x][y] > graph[x+dx[i]][y+dy[i]] and visited[x+dx[i]][y+dy[i]] == 0:
                if (x + dx[i]) == M-1 and (y + dy[i]) == N-1:
                    result.append(0)
                    continue
                dfs(x+dx[i], y+dy[i])
    visited[x][y] = 0


dfs(0,0)
print(len(result))

 

 

[DP+DFS 답안]

import sys

sys.stdin = open('input.txt', 'r')

M, N = map(int, input().split())

vst = [[-1]*N for _ in range(M)]
graph = [[] for _ in range(M)]
dx = [0,0,-1,1]
dy = [1,-1,0,0]

for _ in range(M):
    graph[_] = list(map(int, input().split()))

def dfs(x,y):
    if x == M-1 and y == N-1:
        return 1
    if vst[x][y] != -1:
        return vst[x][y]

    vst[x][y] = 0

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0<=nx<M and 0<=ny<N:
            if graph[x][y] > graph[nx][ny]:
                vst[x][y] += dfs(nx,ny)
    return vst[x][y]

print(dfs(0,0))

 

DP 개념이 여전히 어렵습니다. 

 

크게 세가지 경우의 수로 나누어서

① 목표 지점에 도달했을 때 경우

  : 목표 지점에 도달하기 직전의 위치(x,y)에서의 경로의 수는 1이므로 무조건 return 1을 합니다. (설명이 더 필요함) 

② 방문을 이미 했던 경우 (vst[x][y] != -1)

  : 새로운 경로에서 목표를 향해 찾아가는데, 알고보니 이미 방문을 했던 곳이라면 해당 위치의 경로 수를 호출해서 return합니다. 왜냐? 이미 방문했던 곳은 더이상 DFS를 풀지않기 위해 이미 저장했던 값(memorization)을 불러오는 DP 알고리즘 개념을 활용하는 것입니다.

③ 새로운 곳의 경우 (vst[x][y] == -1)

  : DFS를 실행시키고 결과 값을 해당 배열에 업데이트를 해줍니다. vst[x][y] += DFS(nx, ny)