백준 1520 c++ "내리막 길" -PlusUltraCode-

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

 

 

[필자 사고]

처음 이 문제를 접했을 때 BFS 탐색을 이용했따.

다만 visited배열을 이용하게 되면 모든 경로의 탐색을 구할 수 없게 되었다.

그래서 visited배열을 빼고 작동시키니 시간초과가 발생했다.

N과 M이 각각 500이므로 시간복잡도를 생각해보니

500*500*4 와 더불어 계속 새로운 경로가 곱해지니 2초가 넘어가게 된다.

 

그래서 필자는 DFS탐색을 이용하여 DP count누적을 이용하여 문제를 해결 했따.

다음은 소스코드 해설이다.

 

1. Input() 함수:
   • 먼저, 배열의 크기 N x M을 입력받고, 2차원 배열 arr과 방문 여부를 기록하는 visited 배열을 초기화한다.
   • arr는 각 지점의 높이를 저장하는 배열이며, visited는 특정 좌표에 방문했는지를 기록한다. 처음에는 -1로 초기화되며, 이 visited 배열은 메모이제이션에 활용되어 중복 계산을 방지한다.
2. isInside() 함수:
   • 주어진 좌표가 배열의 범위를 벗어나는지 확인하는 함수이다. 좌표가 배열의 범위 내에 있으면 true, 아니면 false를 반환한다.
3. DFS() 함수:
   • 이 함수는 DFS 방식으로 각 좌표에서 도달 가능한 경로의 수를 구하는 재귀 함수이다.
   • sero, garo는 현재 노드의 좌표를 의미한다.
   • 기저 조건으로 목표 좌표 (N-1, M-1)에 도달하면 1을 반환하여 경로가 하나 존재함을 나타낸다.
   • 이미 방문한 좌표라면(즉, visited[sero][garo]가 -1이 아니라면) 그 값을 바로 반환하여 중복 계산을 방지한다.
   • 다음으로 현재 좌표를 기준으로 4방향(상, 하, 좌, 우)으로 이동 가능한지 확인한다. 이동하려는 좌표가 배열 범위 내에 있고, 그 좌표의 높이가 현재 위치의 높이보다 작다면 이동할 수 있다. 이 경우 재귀적으로 DFS를 호출하여 해당 좌표에서 도달 가능한 경로 수를 구한다.
   • 이렇게 계산된 값은 visited 배열에 저장하여, 동일한 좌표에 대해 중복 계산이 발생하지 않도록 한다.
4. GameStart() 함수:
   • 이 함수는 게임을 시작하는 함수로, (0, 0)에서 시작하여 목표지점 (N-1, M-1)까지 도달할 수 있는 모든 경로의 수를 출력한다. DFS 함수의 반환값을 출력하는 역할을 한다.

핵심 동작 설명:

1. DFS를 이용한 경로 탐색: DFS(0, 0)에서 시작하여 목표 좌표 (N-1, M-1)에 도달할 수 있는 경로의 수를 계산한다.
2. 방문 체크 및 메모이제이션: 이미 방문한 좌표는 visited 배열에 저장된 값을 사용하여 중복 계산을 방지한다.
3. 높이 조건: 다음 노드로 이동할 때는 반드시 현재 노드의 높이보다 낮은 곳으로만 이동할 수 있다.
4. 경로 카운트: 최종적으로 출발점에서 목표점까지 도달할 수 있는 경로의 수를 출력한다.

 

[소스 코드]

 

#include <iostream>
#include <vector>
#include <queue>

using namespace std;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,-1,0,1 };
typedef pair<int, int> Node;

int N, M;
int resultCount = 0;
vector<vector<int>> arr;
vector<vector<int>> visited;

void Input() {
	cin >> N >> M;
	arr.resize(N);
	visited.resize(N);
	for (int i = 0; i < N; i++) {
		arr[i].resize(M);
		visited[i].resize(M,-1);
	}

	for (int i = 0; i < N; i++) {
		for (int k = 0; k < M; k++) {
			int num;
			cin >> num;
			arr[i][k] = num;
		}
	}
}
bool isInside(int sero, int garo) {
	if (sero >= 0 && sero < N && garo >= 0 && garo < M)return true;
	return false;
}

int DFS(int sero, int garo) {
	if (sero == N - 1 && garo == M - 1)return 1;
	if (visited[sero][garo] != -1)return visited[sero][garo];

	visited[sero][garo] = 0;
	for (int i = 0; i < 4; i++) {
		int nextSero = sero + dy[i];
		int nextGaro = garo + dx[i];

		if (isInside(nextSero, nextGaro) == false)continue;
		if (arr[nextSero][nextGaro] < arr[sero][garo]) {
			visited[sero][garo] = visited[sero][garo] + DFS(nextSero, nextGaro);

		}

	}
	return visited[sero][garo];

}

void GameStart() {
	
	cout << DFS(0,0);
}

int main(void) {
	Input();
	GameStart();
}