[백준] 1520번: 내리막 길 C++로 풀어보기

1520번 설명

생각

처음에는 BFS나 DFS를 사용하면 될 것 같다고 생각했는데, 이것만 이용하면 시간 초과가 뜬다.

다이나믹 프로그래밍(DP)를 사용해야 되는데, 

 

다이나믹 프로그래밍은 여러 개의 하위 문제를 먼저 푼 후 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘이다.

 

다이나믹 프로그래밍을 사용하려면 세 가지 과정을 거쳐야 하는데, 바로

1. 테이블 정의하기
2. 점화식 찾기
3. 초기값 정하기

이다.

 

출처: https://blog.encrypted.gg/974

[실전 알고리즘] 0x10강 - 다이나믹 프로그래밍

(밑의 유튜브 강의로도 확인할 수 있다.)

https://www.youtube.com/watch?v=5leTtB3PQu0&list=PLtqbFd2VIQv4O6D6l9HcD732hdrnYb6CY&index=17 

다이나믹 프로그래밍 바킹독님 강의

 

 

코드

#include <bits/stdc++.h>
using namespace std;
int board[502][502];
int dp[502][502];
int n = 0, m = 0; // n = 행의 수, m = 열의 수
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 }; // 상하좌우 네 방향을 의미


int dfs(int x, int y) { 

    if (x == n - 1 && y == m - 1) { // 현재 위치가 우측 하단 모서리라면 
        return 1;
    }

    if (dp[x][y] == -1) {
        dp[x][y] = 0;
        for (int dir = 0; dir < 4; dir++) { // 상하좌우 칸을 살펴본다.
            int nx = x + dx[dir];
            int ny = y + dy[dir]; // nx, ny에 dir에서 정한 방향의 인접한 칸의 좌표가 들어감
            
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) { // 새로운 위치가 보드 범위를 벗어나면 무시
            
            }
            else {
                if (board[nx][ny] < board[x][y]) { // 범위 안이고 새로운 칸의 숫자가 전 칸 숫자보다 작다면
                    dp[x][y] += dfs(nx, ny); // 현재 위치의 dp 값에 새로운 위치에서의 경로 개수를 더해준다
                }
            }
        }
    }
    return dp[x][y];
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> board[i][j]; // 입력
            dp[i][j] = -1; // -1로 초기화
        }
    }
    cout << dfs(0, 0); // 좌측 상단 모서리에서부터 시작
    return 0;
}

일단 배열 dp를 -1로 초기화한다.

그리고 dfs(0,0)을 실행하는데, 상하좌우에 있는 dfs 실행 결과를 현재 위치의 dp 배열에 더해준다.

dfs가 재귀적으로 진행되면서 맨 우측 하단 모서리까지 코드가 진행되고, 그 때는 return 1이 되면서 덧셈이 시작된다.

 

결과

1520번 결과