[백준] 1520번 내리막길

1520 내리막길

문제

---

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

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

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

입력

---

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

출력

---

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

---

풀이)

처음에 완전탐색으로 풀었다가 시간초과가 난 문제이다.

4방향으로 이동이 가능할 뿐더러, 칸이 500 *500 이라서 너무나 많은 경로의 수가 존재한다.

그래서 다른 방법으로,

dfs와 dp를 함께 사용해 이미 검증된 경로는 다시 방문하지 않게 해야하는 문제이다.

dp[i][j] = i번째 행, j번째 열일 때 존재하는 경로의 수 라고 하자.

과정은 이러하다.

1. dp[][]배열을 -1로 초기화 시켜준다,

2. dfs 탐색으로 칸을 방문했을 때 처음 방문한 칸인지, 이전에 방문했던 칸인지 확인한다.

   처음 방문한 칸일경우 - dp[][]를 0으로 바꾸고, 

그 칸에서 목적지까지 갈 수 있을 경우, 경로의 수를 증가시킨다.

   이미 방문했던 칸일 경우 - 그 칸에서 목적지까지의 경로의 수를 반환한다.

위 과정을 예시문제에 적용할경우 dp에 저장되는 값을 그림으로 표현해봤다.

주의점

dp[][]배열을 0으로 초기화하면

어떤 칸에서 목적지까지 갈 수 있는 경로가 없을 경우 dp[][]값도 0인데,

나중에 그 칸을 다시 방문했을 때 처음 방문이여서 0인지 or 목적지까지 갈 수 있는 경로가 없어서 0인지 구별이 불가능하다.

그래서 그 칸에 대한 탐색을 반복하게 된다.

이를 방지하기위해 맨처음에 dp배열을 -1로 초기화하는 것이다.

코드)

#include <stdio.h>
#include <algorithm>
using namespace std;
 
int m, n;
int map[500][500];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
int dp[500][500];
 
int dfs(int y,int x) {
    if (y == m - 1 && x == n - 1) {//제일 오른쪽 아래 = 목적지
        return 1;
    }
    if (dp[y][x] == -1) { //한 번도 방문하지 않은 길이라면
        dp[y][x] = 0;
        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (ny >= 0 && ny < m && nx >= 0 && nx < n && map[ny][nx] < map[y][x]) {
                dp[y][x] += dfs(ny, nx);
            }
        }
    }
    
    return dp[y][x];
}
 
int main() {
    scanf("%d %d", &m,&n);
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &map[i][j]);
            dp[i][j] = -1;
        }
    }
    printf("%d", dfs(0, 0));
    return 0;
}
 

결과)