[BAEKJOON] 1520번 : 내리막 길 *

문 제

 

소 스  코 드

#include <iostream>

void Display(int **, const int&, const int&);
void SearchRoad(int ** , int ** , const int& , const int& , const int& , const int& ); 


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


	int M, N;
	std::cin >> M >> N;

	int **map{ new int*[M] };
	int **dp{ new int *[M] };
	for (int i = 0; i < M; ++i) {
		map[i] = new int[N];
		dp[i] = new int[N];
		std::fill_n(dp[i], N, -1);
	}

	for (int i = 0; i < M; ++i) 
		for (int j = 0; j < N; ++j) std::cin >> map[i][j];

	SearchRoad(map, dp, M, N, 0, 0);

	//Display(dp, M, N);

	std::cout << dp[0][0] << '\n';

	for (int i = 0; i < M; ++i) delete[] map[i];
	delete[] map;

	for (int i = 0; i < M; ++i) delete[] dp[i];
	delete[] dp;

	return 0;
}

void Display(int **map, const int& M, const int& N) {

	for (int i = 0; i < M; ++i) {
		for (int j = 0; j < N; ++j) {
			std::cout << map[i][j] << "  ";
		}
		std::cout << '\n';
	}
}

void SearchRoad(int ** m, int ** dp, const int& M, const int& N, const int& nextM, const int& nextN) {

	if (-1 != dp[nextM][nextN]) return;
	if ((M - 1 == nextM) && (N - 1 == nextN)) {
		dp[nextM][nextN] = 1;
		return;
	} else	dp[nextM][nextN] = 0;


	if ((0 <= nextM - 1) && (m[nextM - 1][nextN] < m[nextM][nextN])) {
		SearchRoad(m, dp, M, N, nextM - 1, nextN);
		dp[nextM][nextN] += dp[nextM - 1][nextN];
	}
	if ((M > nextM + 1) && (m[nextM + 1][nextN] < m[nextM][nextN])) {
		SearchRoad(m, dp, M, N, nextM + 1, nextN);
		dp[nextM][nextN] += dp[nextM + 1][nextN];
	}
	if ((0 <= nextN - 1) && (m[nextM][nextN - 1] < m[nextM][nextN])) {
		SearchRoad(m, dp, M, N, nextM, nextN - 1);
		dp[nextM][nextN] += dp[nextM][nextN - 1];
	}
	if ((N > nextN + 1) && (m[nextM][nextN + 1] < m[nextM][nextN])) {
		SearchRoad(m, dp, M, N, nextM, nextN + 1);
		dp[nextM][nextN] += dp[nextM][nextN + 1];
	}
}

 

풀 이

 

• DFS와 DP를 사용하여 해결 할 수 있는 문제입니다.

 50에서 시작하여 10까지 가는 내리막 경로를 찾는 문제입니다. (왼쪽 표는 dp)

 왼쪽 그래프 부분의 경로를 찾을 경우.

재귀 함수를 통하여 왼쪽 아래에에 도착했을 경우, 

이러한 상태가 된다.

왼쪽 아래에 도착했다는 상태일 경우 1로 다시 길을 되짚어 보며 길의 dp를 채워 나간다.

 

 위에서 했던 방법과 같이 경로를 먼저 검색을 하는데, 이미 지나 갔던 경로, 15(주황색) 이 있을 경우.

같은 길을 다시 찾는 것을 없애고, 32(초록색) 왼쪽, 아래쪽과 같이 경로가 있을 경우, 멈춰서 다른 길을 먼저 검사한다.

 위의 과정을 통하여 3이라는 결과를 얻을 수 있다.

 

출 력 값

 

 

문 제  출 처

문제 링크 : https://www.acmicpc.net/problem/1520

1520번: 내리막 길