[GOLD 3] 내리막 길

1. 문제 링크

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

---

 

2. 문제 이해 및 풀이 전략

높이가 주어진 지도에서 내리막 길만 통해 맵의 오른쪽 하단까지 갈 수 있는 경우의 수를 출력하는 문제.

내리막 길 = 전 방문지의 높이가 현 방문지의 높이가 높은 경우 이기때문에 문제에서 갈 수 있다 말한 상,하,좌,우 방향에서 높이가 낮은 방향으로 진행해 오른쪽 하단 까지 닿는 경우를 출력하면 된다.

 

+ 추가)

문제에서 주어진 가로, 세로의 최대 크기는 500이고 시간 제한은 2초이기 때문에 경로가 구불구불 해지는 경우, 검색해야 할 경로가 많아지면 시간 초과가 발생하기 때문에 탐색 과정을 단축할 방법이 필요하다.

 

때문에 현재 방문한 지역이 몇가지 경로가 이어졌는지를 기록하는, DP에서 자주 사용하는 메모이제이션 기법을 사용해 다시 풀었다.

---

3.  풀이 코드

#include<iostream>
#include <algorithm>
#include <vector>

using namespace std;

#define fastio cin.tie(0)->ios::sync_with_stdio(0); cout.tie(0); setvbuf(stdout, nullptr, _IOFBF,BUFSIZ)

int board[501][501];
int dp[501][501];

int dirX[4] = { 0, 0, -1, 1 };
int dirY[4] = { -1, 1, 0, 0 };

int M, N;

// 풀이
int DFS(int startX, int startY)
{
	// 목적지 도착
	if (startX >= M - 1 && startY >= N - 1)
		return 1;

	// 이미 방문한 곳이면 가짓수 출력
	if (dp[startX][startY] != -1)
		return dp[startX][startY];

	dp[startX][startY] = 0;

	// 상,하,좌,우 탐색 -> 가짓수 더하기
	for (int i = 0; i < 4; i++)
	{
		int nextX = startX + dirX[i];
		int nextY = startY + dirY[i];

		if (nextX < 0 || nextY < 0 || nextX >= M || nextY >= N)
			continue;

		if (board[startX][startY] <= board[nextX][nextY])
			continue;

		dp[startX][startY] += DFS(nextX, nextY);
	}

	return dp[startX][startY];
}

int main()
{
	fastio;

	cin >> M >> N;

	// 입력
	for(int i = 0; i < M; i++)
	{
		for(int j = 0; j < N; j++)
		{
			cin >> board[i][j];
			dp[i][j] = -1;
		}
	}

	cout << DFS(0, 0);

	return 0;
}

---

4. 결과 및 회고

 

많은 경우의 수를 검색하는 문제에서 시간 제한을 넘지 않기 위해 메모이제이션 같은 방법을 사용해 효율성을 높이는 문제가 생각보다 많다. 문제의 유형을 독립적으로 기억하지 말고 언제든 응용할 수 있도록 연습해야 한다.