[C++] 백준 1520 내리막길

문제 링크

---

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

1520번: 내리막 길

 

접근 방법

---

 

 이 문제는 내리막 길(현재보다 더 값이 작은 지점)으로만 따라 갔을 때, 목적지에 도착하는 길의 수를 구하는 문제이며, 문제를 보았을때 DFS를 사용하면 top-down방식으로 가능할 것이고, BFS를 사용하면 bottom-up방식이 가능하다. 필자는 DFS를 이용한 top-down방식으로 해결하였다.

 

(1) 변수

 dp[i][j]는 i,j에서 출발하였을 때, 내리막 길을 따라 도착지에 도착하였을 경우에 대한 길의 수이며, 방문 여부로도 사용된다. 초기값을 0으로 사용하게 되면, 방문을 하였어도 도착지점까지 못 간다면 계속 0이기 때문에 방문여부를 확인하기 어렵기 때문에 초기값을 -1로 하였다.

 

(2) solve()

int &ret = dp[x][y];
if (ret != -1) return ret;
if (x == n && y == m) return ret = 1;
ret = 0;

 함수가 호출되었을때, 가장 먼저 방문여부( if (ret != -1) )를 판단한다. 중복되는 연산을 피하기 위해서이다. 방문을 하였으면 해당 dp에 저장된 값을 return한다. 좀 더 자세히 설명을 하자면 어차피 현재 함수의 x,y에서 갈 수 있는 경로를 이미 다 탐색을 한 값이 dp[x][y]에 저장되어 있으므로 함수를 더 진행시킬 필요가 없다는 것이다.   

 그 다음 도착지점에 도착했다면( if (x == n && y == m) ), 도착한 경로에 대한 경우가 추가 되었으므로 1을 return한다.

 위의 두가지 경우가 아니면 방문을 했다는 의미로 값을 0으로 바꿔준다.

 

for (int i = 0; i < 4; i++) {
		int next_x = x + direction[i].first;
		int next_y = y + direction[i].second;
		if (1 <= next_x && next_x <= n && 1 <= next_y && next_y <= m) 
			if (map[next_x][next_y] < map[x][y]) 
				ret += solve(next_x, next_y);
}

그 이후 현재좌표의 상하좌우 4방향에 대해 map에 포함되어 있는 범위 내에서, 값이 더 작은 곳으로 이동시키면 된다.

소스 코드

---

#include <iostream>
#include <string.h>

using namespace std;
int n, m;
int map[501][501];
int dp[501][501];
pair<int, int> direction[4] = { {1,0}, {0,1}, {-1,0}, {0,-1} };

int solve(int x, int y) {
    
	int &ret = dp[x][y];
	if (ret != -1) return ret;
	if (x == n && y == m) return ret = 1;
	ret = 0;
    
	for (int i = 0; i < 4; i++) {
		int next_x = x + direction[i].first;
		int next_y = y + direction[i].second;
		if (1 <= next_x && next_x <= n && 1 <= next_y && next_y <= m) 
			if (map[next_x][next_y] < map[x][y]) 
				ret += solve(next_x, next_y);
	}
	return ret;
}

int main() {
    
	ios_base::sync_with_stdio(NULL);
	cin.tie(0);
	cout.tie(0);
    
	memset(dp, -1, sizeof(dp));
	cin >> n >> m;
    
	for (int i = 1; i <= n; i++) 
		for (int j = 1; j <= m; j++) 
			cin >> map[i][j];
	cout << solve(1, 1);
}

개발 환경 : VS 2019

질문, 지적 환영입니다.