1520번: 내리막 길

문제 설명

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

1520번: 내리막 길

[문제]

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

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

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

 

[입력]

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

 

[출력]

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

 

[예제 입력 1]

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

[예제 출력 1]

3

---

풀이

 지도에서 길을 찾는 문제이지만, 최단 거리를 탐색하는 문제도 아니고 단순히 가능한 모든 경우의 수를 구하면 되는 문제이니 완전 탐색을 적용하면 된다. 길을 갈 수 있는 조건이 현 위치보다 다음 위치가 더 낮으면 되기 때문에, 이를 바탕으로 한 재귀 호출 함수를 작성하면 된다.

유의할 점

 물론 일정 부분 중복된 경로에 대한 계산을 줄이기 위해 2차원 캐시 벡터를 적용한다. 이 때 캐시 벡터를 단순히 해당 지점과 연결된 경로가 있는지 아닌지 확인하는 것에서 끝나는 게 아니라, -1 값을 적용하여 한 번도 가본 적이 없는 길(값 = -1)인지, 탐색을 해보았지만 경로가 없는 길(값 = 0)인지, 아니면 N개의 경로가 존재하는 길(값 = N)인지 확인하는 방향으로 값을 적용하면 훨씬 효율적이다.

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

using namespace std;

vector<vector<int>> cache;

int searchRoute(int M, int N, vector<vector<int>> &map, int r, int c, int prev) {
	int result = 0;

	if (r<0 || r>=M || c<0 || c>=N) //인덱스 범위 밖
		return 0;

	if (map[r][c] >= prev) //이전 높이 보다 높거나 같은 경우 
		return 0;

	if (r == M - 1 && c == N - 1) //끝에 도달한 경우
		return 1;

	if (cache[r][c] != -1) //한 번도 가본 길이 아닌 경우 캐시 반환
		return cache[r][c];
	//상하좌우 길 탐색
	result += searchRoute(M, N, map, r, c + 1, map[r][c]);
	result += searchRoute(M, N, map, r + 1, c, map[r][c]);
	result += searchRoute(M, N, map, r, c - 1, map[r][c]);
	result += searchRoute(M, N, map, r - 1, c, map[r][c]);
	
	return cache[r][c] = result;//저장한 캐시 반환
}

int main() {
	int M, N, answer = 0;
	vector<vector<int>> map;

	cin >> M >> N;

	for (int i = 0; i < M; i++) {//지도, 캐시 벡터 생성
		vector<int> temp(N, 0);
		vector<int> temp2(N, -1);//-1을 통해 길이 없는 경우인지 안 가본 경우인지 구분
		cache.push_back(temp2);

		for (int j = 0; j < N; j++)
			cin >> temp[j];

		map.push_back(temp);
	}

	answer = searchRoute(M, N, map, 0, 0, 10001);

	cout << answer;

	return 0;
}

---

결과