[백준/BOJ] 1520: 내리막 길

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

1520번: 내리막 길

 

 

---

 

 

문제

---

여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다.

현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다. 위와 같은 지도에서는 다음과 같은 세 가지 경로가 가능하다.

 

 

지도가 주어질 때 이와 같이 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 구하는 프로그램을 작성하시오.

 

입력

---

첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. M과 N은 각각 500이하의 자연수이고, 각 지점의 높이는 10000이하의 자연수이다.

 

출력

---

첫째 줄에 이동 가능한 경로의 수 H를 출력한다. 모든 입력에 대하여 H는 10억 이하의 음이 아닌 정수이다.

 

예제 입력

---

4 5
50 45 37 32 30
35 50 40 20 25
30 30 25 17 28
27 24 22 15 10

 

예제 출력

---

3

 

코드 

---

1) 시간초과 코드

#include <iostream>
using namespace std;

int cnt;
int m, n;
int height[501][501];
int dx[4] = { 0, 0, -1, 1 }, dy[4] = { -1, 1, 0, 0 };

void dfs(int x, int y) {
	if (x == m - 1 && y == n - 1) {
		cnt++;
		return;
	}
	for (int i = 0; i <  4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx >= m || nx < 0 || ny >= n || ny < 0) continue;
		if (height[nx][ny] < height[x][y]) dfs(nx, ny);
	}
}

int main() {
	cin >> m >> n;

	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			cin >> height[i][j];
		}
	}

	dfs(0, 0);

	cout << cnt;
	return 0;
}

 

2) 코드 개선

#include <iostream>
using namespace std;

int m, n;
int dp[500][500];
int height[500][500];
int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { -1, 1, 0, 0 };

int dfs(int x, int y) {
	if (x == 0 && y == 0) return 1;
	if (dp[x][y] != -1) return dp[x][y];

	dp[x][y] = 0;
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx >= m || nx < 0 || ny >= n || ny < 0) continue;
		if (height[nx][ny] > height[x][y]) {
			dp[x][y] += dfs(nx, ny);
		}
	}
	return dp[x][y];
}

int main() {
	cin >> m >> n;

	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			cin >> height[i][j];
			dp[i][j] = -1;
		}
	}

	cout << dfs(m - 1, n - 1);
	return 0;
}

 

---

 

 

처음엔 그냥 지도를 따라서 탐색하다가 종점에 도착하면 카운트를 1씩 증가시도록 간단하게 짰는데 역시 시간초과..! 지점은 최대 250000개이다. 특정 지점에 대해 4방향 모두 매번 탐색한다면 최악 4^250000의 시간 복잡도를 갖는다. 

다음으로는, dp는 출발점부터 특정 지점까지 이동 가능한 경로의 수 라고 생각하고 문제를 풀었다. 특정 지점에 대한 dp가 0일 수도 있기 때문에 탐색 여부를 판단하기 위해서 dp == 0 이라는 수식은 쓸 수 없다. 방문을 위한 자료구조를 선언할까 잠깐 생각했다가 dp의 초기값을 -1로 두고 탐색을 한다면 0으로 바꿔주는게 좋겠다고 생각했다. 나중에 검색을 통해 대표적인 코드들을 살펴볼 때 대부분 같은 방식으로 풀어서 신기했음!

int 타입의 함수를 선언해서 재귀호출한다. 최종적으로 리턴되는 값이 정답이 되도록 하기 위해 도착 지점부터 시작하도록 함수를 구현했다. dp[0][0]은 출발지와 도착지가 같으므로 항상 1을 리턴한다. 만약 특정 지점에 dp값이 -1이 아니라면 계산된 값이 있는 것이므로 4 방향에 대해 탐색하는 대신 계산된 값을 리턴한다. -1이 아니라면 dp의 값을 0으로 바꾸어 준 후(가능한 경로가 없을 수 있음) 4 방향에 대해 dfs탐색을 한다. 이동할 수 있는 경로는 현재 노드가 다음 노드보다 작을 때이다(종점부터 출발지까지 가도록 코드를 짤 것이기 때문).