M*N 사이즈의 2차원 배열 지도의 칸 별 높이가 주어집니다.
이 배열에서 세준이는 내리막길로만 움직이려고 합니다.
사실 경로의 길이라든가 내리막의 경사라든가 하는 건 세준이는 개나 줘버렸습니다.
세준이가 (0,0)에서 출발해서 (M-1,N-1)로 갈 수 있는 경우의 수를 구하세요.
DFS 를 재귀적으로 구현하여 DP와 혼용해서 사용했다. DFS 함수의 리턴값은 "해당 위치에서 (M-1,N-1) 위치로 갈 수 있는 방법의 수"로 하였다.
거창한 기법 같지만 그냥 별거 없다. DFS를 이미 수행한 지점을 다시 만났을 때를 대비하여 "해당 위치에서/출발해서 (M-1,N-1) 위치로 갈 수 있는 방법의 수"(함수의 리턴값)를 저장하는 것이다.
스택을 쓰면 DFS의 구현은 쉬워지지만 (0,0) 위치에서 모든 경우의 수를 리턴 받아야하는 이 코드의 경우 좋지 않다.
DFS를 수행할 때 각 위치에 도착했을 때마다 visited 배열을 1씩 증가시키는 것도 하나의 방법이다.(즉 visited 배열은 (0,0)에서 해당 위치까지 도달 가능한 경우의 수로 마지막엔 visited[m-1][n-1] 참고)
그런데 그렇게 했을 때 위에 말한 DP적으로 이미 순회한 데이터를 참고하는 방법이 통하기 어렵고 직접 반복적으로 방문을 해서 +1을 해줘야한다는 생각이 들었다.(해결 방법을 아신다면 댓글로 공유해주심 감사하겠습니다.)
그래서 차라리 리턴하면서 가능했던 경우의 수를 합산해주자는 생각을 했다.
#include<iostream>
#include<memory.h>
#include<iomanip>
using namespace std;
struct pos {
int i, j;
};
int m, n;
bool inbox(int i, int j) {
return i >= 0 && i < m&& j >= 0 && j < n;
}
int tab[500][500];
//dp적으로 dfs
int visited[500][500];
int di[] = { 1,-1,0,0 };
int dj[] = { 0,0,1,-1 };
int dfs(pos cur) {
int sum_children = 0;
for (int k = 0; k < 4; k++) {
pos ch = pos{ cur.i + di[k],cur.j + dj[k] };
if (inbox(ch.i, ch.j)&&tab[ch.i][ch.j]<tab[cur.i][cur.j]) {
if (visited[ch.i][ch.j] == -1) {
sum_children += dfs(ch);
}
else {
sum_children += visited[ch.i][ch.j];
}
}
}
visited[cur.i][cur.j] = sum_children;
//cout << "합산후 : " << cur.i << " , " << cur.j << endl;
//print_visited();
return visited[cur.i][cur.j];
}
int main() {
cin >> m >> n;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
cin >> tab[i][j];
visited[i][j] = -1;//init as unvisited
}
}
visited[m - 1][n - 1] = 1;
dfs(pos{ 0,0 });
//print_visited();
cout << visited[0][0];
}
이 문제는 아이디어 내느라고 다양한 해결방법이 적용 가능한지 고민했던 문제이므로 파랑색 노트를 보도록하렴