[Baekjoon]백준 1520 내리막 길(골드 3) - C++, Python

문제설명

예제

문제를 살펴보면 제일 왼쪽 위에서 제일 오른쪽으로 이동할 때 아래에 위치한 숫자가 더 작은 경우에만

아래로 이동이 가능하다는 조건이 있다

우선 현재 지도의 상태를 입력받을 배열 하나를 선언해주고, 값을 저장할 2차원 배열을 하나더 선언해주었다

해당 배열은 이전에도 사용하였던 동적 프로그래밍 알고리즘을 위해 만들어주었고,

해당 문제에서는 dp[i][j]는 i부터 j까지 이동가능한 경로의 개수를 저장하게 된다 

(코드를 직접 작성하고 수정하면서 두 배열과 높이, 가로 모두 전역변수로 선언하였음)

#include <iostream>
using namespace std;
int height, width;
int dp[501][501] = {0, };
int map[501][501] = {0, };

이후 해결 과정을 위한 함수를 하나 만들어주었다 위치에 따라 경로를 갱신해야하므로 

기존의 방식처럼 배열만 사용하기에는 한계가 있기 때문에 재귀함수를 이용하였다

만약 해당 제일 오른쪽 아래(목적지)에 도달했다면 return 1을 해주고 아닌 경우 이전에 방문한 곳이 아니라는

가정하에 동서남북 이동가능한 지점을 확인한다 이동 가능한 지점을 확인할 때, 지도의 범위내의 index인지, 

index내라면 내리막길이라 이동이 가능한지 확인이 필요하다

만약 이동이 가능하다면 이전에 구하였던 개수와 해당 위치를 더하여 경로 개수를 갱신하면 된다

#include <iostream>
using namespace std;
int height, width;
int dp[501][501] = {0, };
int map[501][501] = {0, };

int sol(int x, int y) {
    if(x == height-1 && y == width-1)
        return 1;

    int dx[4] = {-1, 1, 0, 0}; // 방향지정
    int dy[4] = {0, 0, -1, 1};
    if(dp[x][y] == -1) {
        dp[x][y] = 0;
        for(int dir = 0; dir < 4; dir++) {
            int new_x = dx[dir] + x;
            int new_y = dy[dir] + y;
            if(new_x >= 0 && new_x < height && new_y >= 0 && new_y < width) { // 지도 범위 안인가?
                if(map[new_x][new_y] < map[x][y]) // 이동 가능한가?
                    dp[x][y] += sol(new_x, new_y); // 가능하다면 경로 개수를 더해줌
            }
        }
    }
    return dp[x][y];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> height >> width;
    for(int i = 0; i < height; i++) {
        for(int j = 0; j < width; j++) {
            cin >> map[i][j];
            dp[i][j] = -1; // -1로 초기화
        }
    }

    cout << sol(0, 0) << endl;

    return 0;
}

C++로 작성하면 다음과 같고, python으로 작성할 경우 조금 다른 점이 존재한다

일단, C++에서는 #include <map>을 한 것이 아니기 때문에 map이라는 이름으로 배열 사용이 가능하지만

python에서는 map 대신 board와 같은 다른 이름을 사용하여야한다 

또한 같은 로직으로 작성하게 되면 RecursionError가 발생한다 따라서

sys.setrecursionlimit(10 ** 9)

를 추가해주어야 오류가 발생하지 않는다

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

def sol(x, y):
    if x == height-1 and y == width-1:
        return 1
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    if dp[x][y] == -1:
        dp[x][y] = 0
        for dir in range(4):
            new_x = dx[dir] + x
            new_y = dy[dir] + y
            if 0 <= new_x < height and 0<= new_y < width:
                if board[new_x][new_y] < board[x][y]:
                    dp[x][y] += sol(new_x, new_y)
    return dp[x][y]
                

height, width = map(int, input().split())
board = []
for i in range(height):
    tmp = list(map(int, input().split()))
    board.append(tmp)
    
dp = [[-1] * width for _ in range(height)]

print(sol(0, 0))