[C++][백준 BOJ] 1520 내리막길 / DP + DFS

c++ 백준 1520 내리막길

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

1520번: 내리막 길

 

해설

⚡ dp[N][M] : 좌표가 (N,M) 일 때 가능한 경로 수

⚡ dp는 -1로 초기화 한다

                 : 경로가 하나도 없을때 0 , N개의 경로가 있을 때 , 방문하지 않았을 때 -1

                 : 방문하지 않았을 때를 검사하기 위해서!

⚡ 시작 좌표에 대해서 DFS

                -> "계단수"이면 dfs로 재귀

                -> if 좌표가 범위를 벗어난다면?  탈출가능, 경로가 하나니까 return 1

                -> if 좌표가 목적지 N-1 , M-1에 도달했다면 ? 경로가 하나니까 return 1   

                -> if 방문했으면 ? 해당 좌표의 dp에 저장된 경로수를 return          

 

 

⚡ dfs이해가 안되서 하나하나 그려봤다 
  : dp [N-1][M-1]을 출력하는 것이 아닌 dp[0][0]를 출력해야 한다 (내가 생각한거랑 반대였다....)

---

코드 

int N , M;
const int MAX = 501;
int arr[MAX][MAX];
int dp[MAX][MAX];

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

int dfs(int x, int y) // dp는 -1로 초기화되어있음
{
	if (x == N - 1 && y == M - 1) // 도착지에 도착하면 ?
	{
		return 1;
	}
	if (dp[x][y] != -1) //방문했으면? 
	{
		return dp[x][y];
	}

	dp[x][y] = 0; //방문은 했으니까 0으로
	for (int i = 0; i < 4; i++)
	{
		int mx = x + dx[i];
		int my = y + dy[i];

		if (mx < 0 || my <0 || mx >= N || my >M) 
		{
			continue;
		}
		
		// 계단수여서 다음으로 넘어갈수 있으면?
		if (arr[mx][my] < arr[x][y]) 
		{
			dp[x][y] = dp[x][y] + dfs(mx, my);
		}
	}

	// 최종 정답을 return?
	return dp[x][y];
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	//백준 1520
	cin >> N >> M;

	for(int i =0;i<N;i++)
	{
		for (int j = 0; j < M; j++) 
		{
			cin >> arr[i][j];
		}
	}
	
	memset(dp, -1, sizeof(dp)); 
	// dp[][]가 -1 : 아직 방문하지 x
	// dp[][]가 0 : 0개 

	int answer = dfs(0, 0);
	cout << answer;
}

 

https://github.com/churush912837465

churush912837465 - Overview