백준 1520 _ 내리막 길

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

1520번: 내리막 길

---

✨ 내 소스 코드

#include<iostream>
using namespace std;
int map[500][500];
int result[500][500] = { -1, };
int M, N;
int moved[4][2] = { {-1,0},{0,-1},{0,1},{1,0} };

int func(int x, int y) {
	//최하단에 도착했을 경우
	if (x == M - 1 && y == N - 1) {
		return 1;
	}
    //이미 방문을 한 길의 경우
	if (result[x][y] != -1) {
		return result[x][y];
	}
    
    //이동 가능한 4가지 경우를 탐색
	for (int i = 0; i < 4; i++) {
		int nextX = x + moved[i][0];
		int nextY = y + moved[i][1];
        //배열 범위에서 벗어나지 않고, 현재 위치보다 높이가 낮은 다음 위치를 탐색
		if (map[x][y] > map[nextX][nextY] && nextX >= 0 && nextY >= 0 && nextX < M && nextY < N) {
			//처음 방문해보는 길의 경우
            if (result[x][y] == -1) {
				result[x][y] = func(nextX, nextY);
			}
            //이미 방문해본 길의 경우
			else {
				result[x][y] += func(nextX, nextY);			
            }	
		}
	}
    //다 탐색을 해보았지만 최하단으로 갈 수 있는 길이 없는 경우 
	if (result[x][y] == -1) {
		result[x][y] = 0;
	}
	return result[x][y];
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
    //모든 길을 -1로 초기화
	fill(&result[0][0], &result[500 - 1][500], -1);
	
	cin >> M >> N;
	for (int i = 0; i < M; i++) {
		for (int j = 0; j < N; j++) {
			cin >> map[i][j];
		}
	}

	func(0, 0);
	cout << result[0][0];

	system("PAUSE");

	return 0;
}

 

🙏 문제 풀이

1 -> 2 -> 3

다음와 같이 알고리즘이 진행

최하단에 도착하였을 때에는 1이라는 값을 반환, 지나온 모든 경로의 값 또한 바꾸어 준다

위의 경우 처럼 계속해서 탐색을 하다가 이미 거쳐본 경로를 만날 때가 존재

해당 경로는 이미 탐색을 해보아서 결과를 알고 있기 때문에, 그 값을 반환하여 값을 더해준다

최종적으로 모든 경로의 수는 [0][0]에 들어있기에 이를 출력

 

위의 경우에는 나타나있지 않지만, 최하단에 도착하지 못하고 끝나는 경우가 발생할 수 있음

최하단에 도착하지 못하였을 때에는 경로의 값을 '0'으로 바꾸어 준다

이미 방문 하였지만, 최하단에는 도착하지 못하는 경로라는 의미

알고리즘이 탐색을 하다가 0을 발견하면, 더 이상 나아가도 최하단에는 도착하지 못하는 경로이기 때문에 그대로 값을 반환하여 더 이상의 탐색을 하지 않게 처리해준다

 

 

⭐ 문제 풀이 결과