이번 문제는 백준의 골드 3 문제 내리막 길 문제이다.
문제를 차근차근 한번 읽고 풀어보도록 하자.
최대 500 X 500 크기의 지도가 주어진다.
이 때, 상하좌우를 이동하며 오른쪽 아래 모서리까지 이동하려고 한다.
단, 오르막길은 힘들기에 반드시 내리막길로만 이동하려고 한다!
주어진 지도에 대해 높이가 낮은 곳으로만 이동하는 것이다.
이 때, 내리막길로만 이동할 수 있는 경로의 수를 계산하라!
DP?
보통 지도 상에서 경로의 수를 계산하는 것은 동적 계획법으로 해결한다.
2차원 배열인 DP[i][j]를 선언하여, 각 칸에 대해 경로를 계산하는 것이다.
이전 경로에 대해서 (i, j) 까지 오는 경로의 수를 더해가는 것이다.
하지만 이번 문제는 조금 다르다.
위의 논리가 적용이 되려면, 사용자는 아래와 오른쪽으로만 움직여야 한다.
왼쪽이나 위로 움직이는 경우는 저런 방식으로 계산할 수 없는 것이다.
그럼 어떤 방식으로 풀어야 할까?
BFS?
그래프의 상하좌우를 모두 탐색할 수 있는 알고리즘은 BFS, DFS가 있다.
둘 중 하나의 방식으로 그래프를 훑으며, Memoization을 진행해야 할 것 같다.
과연 BFS와 DFS 둘 중 어느 알고리즘을 적용해야할까?
먼저 BFS에 대해서 생각을 해보자.
BFS를 이용해서 시작지점부터 상, 하, 좌, 우를 훑으며 탐색을 진행한다.
Memoization의 원리를 생각해보았을 때, 이전 단계의 경로 수를 알아야 한다.
하지만 BFS를 이용하는 경우, 이전 단계와 이어지는 연속성을 이용할 수가 없다.
그럼 DFS에 대해서 한 번 생각해보도록 하자.
DFS!
DFS는 상, 하, 좌, 우 순서가 아닌 깊이를 우선으로 탐색하는 방식이다.
따라서, 이전 단계의 경우의 수를 계속 추적할 수 있다.
하지만, 도착점에 도착할 수 있는 경로의 수를 정하는 것이니, 거꾸로 생각해야 할 것 같다.
재귀 함수를 선언하되, 도착점에 도착할 수 있다면 1을 반환해서 이전 경로에 더하도록 하는 것이다.
방문 여부 검사
이 때 고려해야 할 중요한 부분이 하나 더 있다.
바로 방문 여부를 어떻게 점검할 지 고려를 해야 한다.
방문 여부를 검사하지 않는다면, 방문했던 위치를 또 방문하는 상황이 생길까?
나는 없다고 판단했다.
그 이유는, 오직 내리막길로만 주인공이 이동할 수 있기 때문이다.
이미 내리막길로 판단되어 주인공이 이동했다면, 지나온 길은 모두 현재 칸보다 큰 것이다.
즉 이미 지나온 길로 다시 되돌아 갈 일은 없게 되는 것이다!
그럼 이제 직접 로직을 구현해보도록 하자.
아래와 같이 일단 DFS 로직을 구현해 보았다.
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, 1, 0 , -1 };
int dfs(int curr_x, int curr_y) {
if (curr_x == row - 1 && curr_y == col - 1)
return 1; // 도착 지점에 도달할 수 있으면 1 반환
for (int i = 0; i < 4; i++) {
int nx = curr_x + dx[i];
int ny = curr_y + dy[i];
if ((nx >= 0 && nx < row) && (ny >= 0 && ny < col))
if (downhill[curr_x][curr_y] > downhill[nx][ny])
dp[curr_x][curr_y] += dfs(nx, ny);
// 다음 갈 위치가 가능한 경로일 경우 현재 길에 더해줌
}
return dp[curr_x][curr_y]; // 더 이상 갈 길이 없다면 현재 경로 값 반환
}하지만 이 로직은 시간 초과를 받게 되었다.
논리에는 문제가 없는 것 같은데, 왜 시간 초과가 발생했을까?
바로 위에서 짚고 넘어갔던 방문 처리 때문이다.
내가 말했듯이, 이미 지나온 자리는 항상 크기 때문에 다시 방문할 일이 없다.
하지만 앞선 경우에서 이미 계산한 곳을 다른 경로로써 또 다시 방문하는 경우는?
같은 경로를 반복해서 지나가게 될 것이므로, 이미 지난 길을 또 가는 꼴이 된다!
그럼 도착 지점까지 갈 수 있는 위치라는 것을 알면서도 계속 가게 되는 것이다.
결국 이렇게 되면 우리가 Memoization 방식을 사용하는 의미가 없게 된다!
따라서 다시 방문을 했을 때, 이미 지나온 길이라는 사실을 알고 정보만 얻어가야 한다.
최종적으로 아래와 같이 구현할 수 있다.
int dx[4] = { -1, 0, 1, 0 }; // 위로 갈 필요없음
int dy[4] = { 0, 1, 0 , -1 };
int dfs(int curr_x, int curr_y) {
if (curr_x == row - 1 && curr_y == col - 1)
return 1; // 도착 지점에 도달할 수 있으면 1 반환
if (dp[curr_x][curr_y] != -1)
return dp[curr_x][curr_y];
dp[curr_x][curr_y] = 0; // 처음 오는 경로는 반드시 0으로 초기화
for (int i = 0; i < 4; i++) {
int nx = curr_x + dx[i];
int ny = curr_y + dy[i];
if ((nx >= 0 && nx < row) && (ny >= 0 && ny < col))
if (downhill[curr_x][curr_y] > downhill[nx][ny])
dp[curr_x][curr_y] += dfs(nx, ny);
// 다음 갈 위치가 가능한 경로일 경우 현재 길에 더해줌
}
return dp[curr_x][curr_y]; // 더 이상 갈 길이 없다면 현재 경로 값 반환
}이 방식이 바로 흔히 부르는 Top-Down 방식의 Memoization이다!