💡 깊이 우선 탐색/다이나믹 프로그래밍/그래프 이론/그래프 탐색
Memory 4040KB Time 40ms Code Length 695B
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<stdio.h>
#include<algorithm>
using namespace std;
int map[500][500];
int visited[500][500];
int dp[500][500];
int m, n;
int dy[] = { -1,1,0,0 };
int dx[] = { 0,0,-1,1 };
int dfs_dp(int y, int x) {
if (y == m-1 && x == n-1 ) return 1;
if (visited[y][x])return dp[y][x];
visited[y][x] = 1;
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (ny < 0 || nx < 0 || ny >= m || nx >= n) continue;
if (map[y][x] > map[ny][nx]) {
dp[y][x] += dfs_dp(ny, nx);
}
}
return dp[y][x];
}
int main() {
scanf("%d %d", &m, &n);
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
scanf(" %d", &map[i][j]);
}
}
printf("%d",dfs_dp(0,0));
}
이 코드는 주어진 m x n 크기의 2차원 배열(map)에서 (0, 0)에서 출발하여 (m-1, n-1)까지 이동할 수 있는 경로의 수를 구하는 문제를 해결한다.
- dfs_dp 함수는 현재 위치에서 상하좌우로 이동하면서 갈 수 있는 경로의 수를 재귀적으로 탐색한다. 이미 방문한 지점이면 해당 위치의 값을 반환하고, 아직 방문하지 않은 지점이면 해당 위치를 방문 처리하고 이동 가능한 경로를 탐색한다.
- main 함수에서는 배열의 크기와 각 위치의 값을 입력받은 후, dfs_dp 함수를 호출하여 (0, 0)에서 출발하여 (m-1, n-1)까지의 경로 수를 출력한다.
