[백준] No.1520 - 내리막 길 (C++)

문제

www.acmicpc.net/problem/1520

1520번: 내리막 길

 

풀이

다이나믹 프로그래밍과 DFS가 결합된 문제이다.

 

메모이제이션으로 값을 재사용하는 최적화를 하기 위해서는 어떤 부분에서 중복된 계산이 이루어지는지 확인해야 한다.

해당 문제에서 DFS로 시작점에서 더 작은 수로 재귀 호출을 한다고 해보자.

 

문제에서 주어진 예제는 아래와 같다.

출발점인 50에서 45로 분기하였다고 가정하면 32에서 20이나 30으로 진행하는 두 가지 경로로 나뉜다.

해당 호출들에서는 아래와 같이 노란색이 칠해진 경로가 동일하게 사용된다. 

따라서 우리는 이미 탐색이 진행된 경로의 값을 다시 사용한다면 중복의 계산을 없애고 최적화할 수 있다는 것을 알 수 있다.

 

route_count[500][500] 배열을 통해 해당 위치가 가지는 경로의 가지 수를 저장하는 DFS를 구현하자.

 

해당 위치 (r,c)에서 인접 값들 중에 더 작은 값이 있다면 해당 위치를 재귀 호출하여 해당 위치가 가지는 경로 수들을 모두 합하여 route_count[r][c]에 기록해 둔 후에 반환한다.

 

코드

	#include <iostream>
	#include<string.h>
	using namespace std;
	int row,col;
	int map[500][500];
	int route_count[500][500];
	int move_row[4] = {0,1,0,-1};
	int move_col[4] = {1,0,-1,0};
	int findDownRoute(int r, int c){
	if(r==row-1 && c== col-1)
	return 1;
	int& ret = route_count[r][c];
	if(ret != -1)
	return ret;
	ret =0;
	int next_r,next_c;
	for(int i=0; i<4 ; ++i){
	next_r = r+move_row[i];
	next_c = c+ move_col[i];
	if(0<=next_r&& next_r<row && 0<=next_c && next_c<col)
	if(map[r][c] > map[next_r][next_c])
	ret += findDownRoute(next_r, next_c);
	}
	return ret;
	}
	int main() {
	cin>>row>>col;
	for(int i=0; i<row ; ++i)
	for(int j=0; j<col ; ++j)
	cin>>map[i][j];
	memset(route_count, -1, sizeof(route_count));
	cout<<findDownRoute(0, 0)<<"\n";
	return 0;
	}

view raw [BaekJoon]_1520_내리막 길.cpp hosted with ❤ by GitHub