Baekjoon1520-내리막 길

백준 사이트 1520 - 내리막 길 문제입니다.

1. 문제

https://www.acmicpc.net/problem/1520

---

2. Input , Output

---

3. 분류 및 난이도

DP와 DFS의 혼합 문제입니다.
꽤나 어려웠습니다.
백준에서는 Gold4의 난이도를 책정하고 있습니다.

---

4. 생각한 것들

• BFS로 풀 수 있는가?
  • 시도한 사람들은 있습니다. 저는 시도하다가 메모제이션과 연결하기 어려워서 포기했습니다.
• 메모제이션과 DFS의 연결
  • 이것이 핵심입니다. DFS 동작방식을 잘 알고 있어야 풀 수 있는 것 같습니다.

---

5. code

#include<iostream>
#include <queue>
#include<cstring>
using namespace std;

const int MAX = 501;

int N, M;
int MAP[MAX][MAX] = { 0, };
int dp[MAX][MAX];

int dx[4] = { -1, 0,1,0 };
int dy[4] = { 0,1,0,-1 };

void Input()
{
	cin >> N >> M;
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < M; ++j)
		{
			cin >> MAP[i][j];
			dp[i][j] = 0;
		}
	}

}

int DFS(int i, int j)
{
	if (i == N - 1 && j == M - 1)
		return 1;
	if (dp[i][j] != -1)
		return dp[i][j];
	dp[i][j] = 0;
	for (int k = 0; k < 4; ++k)
	{
		int newx = i + dx[k];
		int newy = j + dy[k];
		if (0 <= newx && newx < N && 0 <= newy && newy < M && MAP[newx][newy] < MAP[i][j])
		{
			dp[i][j] += DFS(newx, newy);
		}
	}
	return dp[i][j];
}

void Solve()
{
	//DFS
	memset(dp, -1, sizeof(dp));
	cout << DFS(0, 0);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	Input();
	Solve();
}

---

6. 후기

코드는 짧지만 어려웠습니다.