▶문제
▶DFS
우선, 이 문제를 풀기 위해 DFS(깊이 우선 탐색)에 대해 알아야한다.
[참고]
DFS
Depth-First Searh, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이며 스택 자료구조(혹은 재귀함수)를 이용한다.
DFS의 작동 방법
1. 노드와 연결된 탐색하지 않은 이웃 노드 중 하나를 탐색한다.
2. 탐색하지 않은 이웃 노드가 없는 경우 이전 노드로 돌아간다. 그 후 다른 탐색하지 않은 이웃 노드를 탐색한다.
*여러 개의 선택지가 있을 때 일관성이 있게 노드를 선택할 것. ex)가장 작은 번호의 노드부터...
그러나, DFS는 탐색 가능한 노드를 모두 다 탐색해보기 때문에 DFS만으로는 시간 내에 풀지 못한다.
따라서, DP를 같이 활용하여 연산 시간을 줄여야한다.
▶DP
Dynamic Programming. 앞에서 계산한 식을 배열에 미리 저장하여 연산속도를 증가시키는 프로그래밍이다.
사용조건
① 최적 부분 구조: 큰 문제를 작은 문제로 나누어 작은 문제의 답을 모아 큰 문제 해결
② 중복 부분 문제: 동일한 부분 문제를 반복적으로 해결
-> 여기선 임의의 점 (x,y)에서 도착 지점까지 가는 경로를 세분화하여 구한다면 그 이후에는 (x,y)에 도착하기만 하면 그때부터 경우의 수는 구할 필요 없다. 즉, 도착 지점까지의 가는 경우의 수는 임의의 점에서 도착 지점까지 가는 경우의 수를 합친 것과 같아진다. 따라서 이 문제에선 DP를 사용할 수 있다.
작동방식
① 탑다운: 하향식(위에서 아래)
한번 계산한 결과를 메모리에 저장하는 메모이제이션을 수행한다. 후에 같은 문제를 다시 호출하면 메모한 결과를 그대로 가져오면 된다.
② 보텀업: 상향식(아래에서 위)
작은 문제 + 큰 문제 = 큰 문제가 되는 형식. 반복문을 사용한다.
▶풀이
전체 코드
<코드별 해석>
① 1~3번째 줄: 이 부분은 기본 설정하는 부분 같은데 잘 모르겠어서 검색을 해보았다.
→ sys.stdin.readline을 input 함수로 사용한다. 또한, 큰 값을 설정함으로써 재귀 호출이 많이 필요한 경우에도 오버플로우가 발생하지 않도록 보호할 수 있다.
※ 재귀 함수를 사용할 때 파이썬은 최대 재귀 호출 깊이를 1000으로 제한한다. 이를 더 높은 값으로 설정하여 재귀 호출 깊이에 대한 제한을 풀어줘야 한다.
② 5~8번째 줄: 행과 열의 개수를 입력 받는다. 그 후 내리막길 개수를 저장할 dp 테이블을 초기화 하고 문제 속 그래프 정보를 입력 받는다.
③ 10~26번째 줄: 해당 위치에서 출발하여 내리막길의 개수를 계산하는 dfs 함수를 정의하였다.
함수를 수행하면서 내리막길의 개수를 누적한다. 현재 위치보다 높이가 낮은 내리막길로만 이동하도록 하였다.
시작지점 - (0,0)
종료조건 - 도착 지점에 도달한 경우 1을 반환한다.
이미 방문한 적 있는 경우 - 해당 위치의 내리막길 개수를 반환한다.
마지막으로 dfs 함수를 호출하여 결과를 출력한다.
매우 어렵다고 느낀 문제였다. 그치만 DPS와 DP 개념에 대해 알게된 좋은 문제였다.
'2024 SWLUG > 백준' 카테고리의 다른 글
| 3주차_백준 (2) - 부녀회장이 될테야 (0) | 2024.05.22 |
|---|---|
| 3주차_백준 (1) - 1,2,3 더하기 (0) | 2024.05.22 |
| 2주차_백준 (2) - 양팔저울 (0) | 2024.05.22 |
| 1주차_프로그래머스 (2) - 공배수 (0) | 2024.05.22 |
| 1주차_프로그래머스 (1) - n의 배수 (0) | 2024.05.22 |