[BAEKJOON/ 백준] 1520번: 내리막 길 (Python)

 

---

[1] 정답 코드

 

import sys
sys.setrecursionlimit(10**5)
input=sys.stdin.readline

M,N=map(int, input().split())
plan=[list(map(int, input().split())) for _ in range(M)]
route=[[-1]*N for _ in range(M)]

dx=[1,-1,0,0]
dy=[0,0,1,-1]
def dfs(start):
    x,y=start
    if x==M-1 and y==N-1: return 1
    if route[x][y]!=-1: return route[x][y]
    route[x][y]=0
    for i in range(4):
        nx=x+dx[i]
        ny=y+dy[i]
        if nx<0 or nx>=M or ny<0 or ny>=N: continue
        if plan[nx][ny]<plan[x][y]: route[x][y]+=dfs([nx,ny])
    return route[x][y]
dfs([0,0])
print(route[0][0])

 

1. import sys: sys 모듈을 임포트한다.

 

2. sys.setrecursionlimit(10**5): 재귀 호출의 최대 깊이를 설정한다. 이는 파이썬 인터프리터에서 재귀 호출의 깊이 제한을 늘려준다.

 

3. input=sys.stdin.readline: input 함수에 sys.stdin.readline을 할당하여 입력 속도를 빠르게 만든다.

 

4. M,N=map(int, input().split()): 첫 번째 줄에서 M과 N을 입력받는다. M은 행의 개수, N은 열의 개수를 의미한다.

 

5. plan=[list(map(int, input().split())) for _ in range(M)]: 이어지는 M개의 줄에서 MxN 크기의 미로 정보를 입력받아 2차원 리스트인 plan에 저장한다. plan[i][j]는 (i, j) 위치의 높이를 의미한다.

• input().split(): input() 함수를 호출하여 사용자로부터 한 줄의 입력을 받는다. 그리고 split() 함수를 사용하여 문자열을 공백을 기준으로 분리하여 리스트로 만든다. 이렇게 하면 한 줄에 입력된 값들이 리스트의 요소로 들어가게 된다.
• list(map(int, ...)): 분리된 각 요소들을 정수형으로 변환한다. map() 함수를 사용하여 각 요소에 대해 정수형으로 변환하는 작업을 한다. 이렇게 하면 문자열 형태의 숫자들이 정수형으로 변환되어 리스트에 들어가게 된다.
• list(map(int, input().split())): 결국 한 줄에 입력된 문자열을 공백을 기준으로 분리하여 정수형으로 변환한 값을 리스트로 만든다. 이 과정을 M번 반복하므로, M개의 리스트가 생성된다.
• [... for _ in range(M)]: 리스트 컴프리헨션을 사용하여 M개의 리스트를 생성한다. _ 변수는 반복문에서 사용되지 않는 값을 무시하고자 할 때 사용되는 관례적인 변수이다. 여기서는 _를 사용하여 반복문에서 사용되는 변수를 명시적으로 무시하고 있다.
• plan=: 생성된 리스트들을 plan 변수에 할당하여 저장한다. 이렇게 하면 MxN 크기의 2차원 리스트가 만들어지게 된다. 각 요소인 plan[i][j]는 (i, j) 위치의 높이를 의미한다.

 

6. route=[[-1]*N for _ in range(M)]: MxN 크기의 2차원 리스트 route를 생성한다. route[i][j]는 출발지(0, 0)에서 (i, j)까지의 경로 수를 저장한다. 초기값은 -1로 설정된다.

 

• [-1]*N: N개의 -1로 이루어진 리스트를 생성한다. 이렇게 하면 한 행의 초기값이 된다. 만약 N이 3이라면 [-1, -1, -1]이 된다.
• [...] for _ in range(M): 리스트 컴프리헨션을 사용하여 M개의 리스트를 생성란다. 각 리스트는 N개의 -1로 이루어진 행이 되며, 전체적으로 MxN 크기의 2차원 리스트가 생성된다. _ 변수는 반복문에서 사용되지 않는 값을 무시하고자 할 때 사용되는 관례적인 변수이다.
• route=: 생성된 2차원 리스트를 route 변수에 할당하여 저장한다. 이렇게 하면 출발지(0, 0)에서 각 위치 (i, j)까지의 경로 수를 저장할 수 있는 route 리스트가 만들어지게 된다. 초기값으로는 모든 위치의 경로 수가 -1로 설정되어 있다.

 

7. dx=[1,-1,0,0], dy=[0,0,1,-1]: 상하좌우로 이동할 때의 x축과 y축 이동 거리를 저장한다.

 

8. def dfs(start):: DFS 알고리즘을 정의한다. start는 현재 위치를 나타내는 리스트 [x, y]이다.

 

9. x, y = start: 현재 위치를 가져온다.

 

10. if x==M-1 and y==N-1: return 1: 만약 현재 위치가 도착지점인 경우 1을 반환하고 재귀를 종료한다.

 

11. if route[x][y] != -1: return route[x][y]: 만약 현재 위치까지의 경로 수가 이미 계산되어 있으면 이를 반환한다.

 

12. route[x][y] = 0: 현재 위치까지의 경로 수를 0으로 초기화한다.

 

13. for i in range(4):: 상하좌우로 이동하며 각 방향으로 탐색한다.

 

14. nx = x + dx[i], ny = y + dy[i]: 다음 이동할 위치를 계산한다.

 

15. if nx < 0 or nx >= M or ny < 0 or ny >= N: continue: 미로 범위를 벗어나는 경우에는 탐색을 진행하지 않고 다음 방향으로 넘어간다.

 

16. if plan[nx][ny] < plan[x][y]: route[x][y] += dfs([nx, ny]): 현재 위치의 높이보다 낮은 위치로만 이동할 수 있으므로, 다음 위치가 현재 위치보다 낮은 높이를 가지고 있다면 해당 위치까지의 경로 수를 계산하여 route[x][y]에 더해준다.

 

17. return route[x][y]: 현재 위치까지의 경로 수를 반환한다.

 

18. dfs([0,0]): 출발지(0, 0)에서 시작하여 DFS 알고리즘을 실행한다.

 

19. print(route[0][0]): 출발지(0, 0)에서 도착지(M-1, N-1)까지의 경로 수를 출력한다.

 

---

sys.setrecursionlimit()

 

파이썬 인터프리터는 기본적으로 재귀 호출에 대한 최대 깊이(재귀 스택의 깊이)를 제한하고 있다. 이는 너무 많은 재귀 호출이 발생하여 스택이 너무 깊어지는 것을 방지하기 위한 것이다. 하지만 때로는 특정한 문제를 해결하기 위해서는 기본 제한을 늘려야 할 때가 있다.

sys.setrecursionlimit() 함수는 파이썬에서 재귀 호출의 최대 깊이를 설정하는 함수이다. 이 함수를 사용하여 재귀 호출의 깊이 제한을 늘릴 수 있다. 인자로는 정수값을 받으며, 이 값은 재귀 호출의 최대 깊이를 나타낸다.

 

sys.setrecursionlimit(10**5)은 재귀 호출의 최대 깊이를 10의 5승, 즉 100,000으로 설정한다. 이렇게 하면 더 깊은 재귀 호출이 가능해지며, 일부 복잡한 알고리즘을 구현할 때 유용하다.

그러나 주의할 점은 재귀 호출의 깊이 제한을 너무 크게 늘리면 스택 오버플로우(Stack Overflow) 오류가 발생할 수 있으며, 이는 프로그램의 비정상적인 종료를 유발할 수 있다. 따라서 깊이 제한을 변경할 때에는 신중하게 결정해야 한다.

 

---

스택 오버플로우(Stack Overflow)

 

소프트웨어에서 스택 오버플로(영어: stack overflow)는 스택 포인터가 스택의 경계를 넘어설 때 일어난다. 호출 스택은 제한된 양의 주소 공간을 이루며 대개 프로그램 시작 시 결정된다.

프로그램이 호출 스택에서 이용 가능한 공간 이상을 사용하려고 시도할 때 또는 지정된 시스템 메모리 사이즈보다 과다한 스택 메모리를 사용할 때 스택 오버플로(overflow)가 발생하며 이 경우 일반적으로 데이터 유실 등 '에러 발생'이 수반된다.

 

 

---

input=sys.stdin.readline

 

함수를 변수에 할당하여 다른 이름으로 사용할 수도 있다. 또한, 함수를 다른 함수의 매개변수로 전달하여 콜백(callback) 함수로 활용할 수도 있다.

 

 

---

[2] 필요한 배경 지식

 

이 문제는 DP(Dynamic Programming)를 사용하여 DFS(Depth-First Search) 문제를 최적화하는 방법으로 풀어야 한다.

 

 

1. DP(Dynamic Programming)란?

 

복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다.

분할 정복(Divide and Conquer)과 유사하며, 분할 정복과의 차이점은 동적 프로그래밍은 중복되는 부분 문제가 발생할 때, 그것을 한 번만 계산하고 그 결과를 메모이제이션(Memoization)하여 다른 비슷한 부분 문제들이 다시 발생할 때, 메모이제이션된 결과를 가져와 재활용한다는 것이다.

 

 

 

동적 프로그래밍을 적용하기 위해서는 다음의 두 가지 조건을 만족해야 한다.

 

• 최적 부분 구조(Optimal Substructure): 전체 문제의 최적해가 부분 문제의 최적해로부터 구해질 수 있어야 한다. Fibonacci 수열의 경우 첫번째 두번째 수열은 각각 1로 고정되어 있다. (편의상 0번째 항이 0이 되는 경우도 있다.) 즉, 3번째 수열은 언제나 결과가 2이다. 또 4번째 수열은 3번째 수열과 2번째 수열을 이용해 구하므로 언제나 정답이 같다는 사실을 알 수 있다.
  
  
• 중복되는 부분 문제(Overlapping Subproblems): F(5)를 구하기 위해서는 F(4), F(3)이 필요하다. 다시 F(4)를 구하기 위해서는 F(3),F(2)가 필요하다. 이 경우를 살펴보면 F(5)에서도 F(3)이 필요하고 F(4)에서도 F(3)이 필요함을 알 수 있다. 즉, 부분 문제가 중복되어 여러번 반복 계산되어야 한다.

 

 

 

2. 메모이제이션 (Memoization)

메모이제이션(memoization)은 동적 프로그래밍(Dynamic Programming) 기법 중 하나로, 함수의 실행 결과를 저장하여 이후 같은 입력이 들어올 때 다시 계산하지 않고 저장된 값을 불러와서 재활용하는 최적화 기법이다.

메모이제이션은 함수의 결과 값을 저장하는 캐시(Cache)를 이용하여 동작한다. 함수를 호출할 때마다 입력 값에 대한 결과 값을 캐시에 저장한다. 이후 같은 입력이 들어올 때는 함수를 실행하지 않고 저장된 값을 바로 반환한다. 이렇게 하면 함수를 반복해서 호출할 때마다 계산하는 시간을 절약할 수 있으며, 함수의 실행 속도를 대폭 향상시킬 수 있다.

 

 

메모이제이션을 사용하기 위해서는 다음과 같은 조건이 필요하다.

• 문제는 부분 문제로 나눌 수 있어야 한다.
• 부분 문제는 중복되어야 한다.
• 부분 문제의 해결 결과를 저장하고 재사용할 수 있어야 한다.

 

메모이제이션은 대부분의 동적 프로그래밍 문제에서 사용되며, 재귀 함수를 이용한 Top-Down 방식으로 구현하는 경우가 많다.

하지만 Bottom-Up 방식으로도 구현할 수 있으며, 이 경우에도 부분 문제의 해결 결과를 배열 또는 리스트에 저장하여 재활용한다.

 

 

출처:

https://galid1.tistory.com/507

https://ai-sinq.tistory.com/entry/%EB%8F%99%EC%A0%81-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D-Dynamic-Programming-DP

 

 

3. 동적 프로그래밍의 구현 방법

 

➰Top-Down

Top-Down은 분할 정복과 비슷한 구조를 가지고 있다. 전체 문제를 작은 부분 문제로 나누고, 그 부분 문제들을 해결하기 위해 재귀적으로 동작한다. 이 때, 중복되는 부분 문제들을 해결하기 위해 메모이제이션(Memoization)이라는 기법을 사용한다. 이는 부분 문제의 결과를 캐시하여 재활용하는 것을 말한다.

Top-Down 방식은 일반적으로 재귀함수를 이용하여 구현한다. 따라서 코드의 가독성이 높아지지만, 많은 스택 메모리를 사용할 수 있으며, 메모이제이션의 처리 오버헤드가 존재할 수 있다.

 

➰Bottom-Up

Bottom-Up은 재귀적인 호출 없이, 작은 부분 문제들을 먼저 해결하고, 그 결과를 이용해 전체 문제의 최적해를 구하는 방식이다. 이 때, 이전에 계산한 결과를 배열 또는 리스트 등의 자료구조에 저장하고, 그 결과를 이용해 다음 계산을 수행한다.

Bottom-Up 방식은 일반적으로 반복문을 이용하여 구현한다. 따라서 코드의 가독성은 낮아질 수 있지만, 많은 반복문을 이용하기 때문에 스택 메모리를 사용하지 않아 메모리 절약 효과가 있으며, 메모이제이션의 처리 오버헤드가 없다.

 

 

 

4. DFS(Depth-First Search)란?

 

트리나 그래프를 탐색하는 기법 중 하나로, 시작 노드에서 자식의 노드들을 순서대로 탐색하면서 깊이를 우선으로 탐색하는 알고리즘이다.

DFS는 주로 반복문을 활용하거나, 재귀문을 통하여 구현된다.

 

탐색 과정이 시작 노드에서 한없이 깊이 진행되는 것을 막기 위해 깊이 제한(depth bound)을 사용한다. 깊이 제한에 도달할 때까지 목표노드가 발견되지 않으면 최근에 첨가된 노드의 부모노드로 되돌아와서, 부모노드에 이전과는 다른 동작자를 적용하여 새로운 자식노드를 생성한다.
여기서 부모노드로 되돌아오는 과정을 백트래킹(backtracking)이라 한다.

 

DFS의 기본 탐색 과정은 특정 정점에서 시작하여 역추적(backtracking) 하기 전에 각 분기를 따라 가능한 한 멀리 탐색하는 것이다.

 

탐색하는 과정은 다음과 같다.

1. 현재 노드를 방문한 것으로 표시한다.

2. 방문한 표시가 되어 있지 않은 각각의 인접한 정점을 탐색한다.

3. 더 이상 방문하지 않은 정점이 없으면 이전 정점으로 역추적(backtracking) 한다.

4. 모든 정점을 방문할 때까지 프로세스를 반복한다.

 

 

 

 

 

 

장점

• 단지 현 경로상의 노드들만을 기억하면 되므로 저장공간의 수요가 비교적 적다.
• 목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.

 

단점

• 해가 없는 경로에 깊이 빠질 가능성이 있다. 따라서 실제의 경우 미리 지정한 임의의 깊이까지만 탐색하고 목표노드를 발견하지 못하면 다음의 경로를 따라 탐색하는 방법이 유용할 수 있다.
• 얻어진 해가 최단 경로가 된다는 보장이 없다. 이는 목표에 이르는 경로가 다수인 문제에 대해 깊이우선 탐색은 해에 다다르면 탐색을 끝내버리므로, 이때 얻어진 해는 최적이 아닐 수 있다는 의미이다.

 

 

출처:

https://olrlobt.tistory.com/35

, 나무위키

---

[3] 느낀 점

 

DP와 DFS 개념에 대해 알 수 있었다.

그런데 이 개념을 활용하여 코드를 작성하는 것은 많이 어려운 것 같다!

관련 문제를 풀어보며 연습을 하면 좋을 것 같다.