[Baekjoon Online Judge] 백준 1520번 내리막 길(C++, Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 1520번 내리막 길

(C++, Python)

(글쓴날 : 2020.04.20)

 

---

* Baekjoon Online Judge, 백준 1520번 문제 C++, Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 1520번 내리막 길

---

1) 문제

문제 링크 : https://www.acmicpc.net/problem/1520

1520번: 내리막 길

---

2) 풀이 과정

* 시간 복잡도 : O(nm)

 

현재 지점에서 상하좌우 낮은 곳으로만 이동이 가능한 N X M 크기의 높이가 적혀 있는 2차원 배열이 주어지고, 제일 왼쪽 위 칸을 출발 지점 제일 오른쪽 아래 칸을 도착 지점으로 할 때, 이동 가능한 경로의 수를 구하는 문제입니다.

 

저의 경우, DFS와 동적 계획법을 적용하였으며, C++과 Python을 사용했습니다.

처음에 Bottom-up 방식으로 계속 접근하였으나, 아래 칸으로도 갈 수 있는 경우를 도저히 해결하지 못해, 풀이 방법을 검색 후 Top-down 방식으로 전환하여 풀었습니다.

 

풀이는 아래의 제가 참고한 블로그와 같습니다.

다만, 참고한 블로그의 코드에 에러가 한 가지 있는데, 방향 벡터를 연산하는 부분에 예외 처리를 해놓지 않으셔서 런타임 에러가 발생하므로 직접 해결하시거나, 제 코드를 참조하시면 되겠습니다.

그리고, 만약 Python을 사용하실 경우 setrecursionlimit()을 사용해 재귀 깊이를 늘려주셔야 런타임 에러가 발생하지 않습니다!

 

* 참고 블로그 : https://simsimjae.tistory.com/23

---

3) 코드

 

* C++ 코드

#include <iostream>
#include <cstring>
 
using namespace std;
 
int N, M;
int MAP[501][501];
int memoization[501][501];
int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};
 
int DFS(int i, int j)
{
    if (!i && !j)
        return 1;
    if (i < 0 || i >= N || j < 0 || j >= M)
        return 0;
    if (memoization[i][j] != -1)
        return memoization[i][j];
 
    memoization[i][j] = 0;
 
    int ii = 0;
    int jj = 0;
 
    for (int way = 0; way < 4; way++)
    {
        ii = i + dx[way];
        jj = j + dy[way];
 
        if (ii < 0 || ii >= N || jj < 0 || jj >= M)
            continue;
 
        if (MAP[ii][jj] > MAP[i][j])
            memoization[i][j] += DFS(ii, jj);
    }
 
    return memoization[i][j];
}
 
int main(void)
{
    ios_base::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 >> MAP[i][j];
 
    memset(memoization, -1, sizeof(memoization));
 
    cout << DFS(N - 1, M - 1);
 
    return 0;
}

---

* Python 코드

import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
 
 
def DFS(i, j):
    if not i and not j:
        return 1;
    if (i < 0 or i >= N or j < 0 or j >= M):
        return 0;
    if memoization[i][j] != -1:
        return memoization[i][j];
    
    memoization[i][j] = 0
 
    for way in range(4):
        ii = i + dx[way]
        jj = j + dy[way]
 
        if ii < 0 or ii >= N or jj < 0 or jj >= M:
            continue
        
        if MAP[ii][jj] > MAP[i][j]:
            memoization[i][j] += DFS(ii, jj)
 
    return memoization[i][j]
    
 
N, M = map(int, input().split())
MAP = [list(map(int, input().split())) for _ in range(N)]
memoization = [[-1] * M for _ in range(N)]
dx, dy = [0, 0, 1, -1], [1, -1, 0, 0]
 
print(DFS(N - 1, M - 1))

---