BOJ 1520 : 내리막 길

• 문제 링크 : boj.kr/1520
• 난이도 : G3
• 태그 : DP, DFS

1520번: 내리막 길

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};

int board[502][502];
int dp[502][502];
int m, n;

int dfs(int cx, int cy) {
    if(cx == n && cy == m) {
        return 1;
    }

    int &ret = dp[cx][cy];
    if(ret != -1) return ret;

    ret = 0;
    for(int i = 0; i < 4; i++) {
        if(board[cx][cy] > board[cx+dx[i]][cy+dy[i]]) {
            ret += dfs(cx+dx[i],cy+dy[i]);
        }
    }
    return ret;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> m >> n;

    for(int i = 1; i <= m; i++) {
        for(int j = 1; j <= n; j++) {
            cin >> board[j][i];
        }
    }
    for(int i = 0; i < m; i++) {
        board[0][i] = board[n+1][i] = 10001;
    }
    for(int i = 0; i < n; i++) {
        board[i][0] = board[i][m+1] = 10001;
    }
    for(int i = 0; i < 502; i++) {
        for(int j = 0; j < 502; j++) {
            dp[i][j] = -1;
        }
    }
    cout << dfs(1,1) << "\n";
    
    return 0;
}

---

풀이

도착점에 도달하는 경로가 존재하는지 찾는 문제는 기본적으로는 DFS를 사용해서 풀 수 있다.

여기서 visit배열을 약간 변형하여 해당 지점에서 도착점까지 도달하는 경로의 수를 저장하여 경로의 수를 찾을 수 있다.

 

이런 배열을 탐색하는 문제에서 좋아하는 테크닉이 하나 있는데, 배열의 인덱스로 배열의 범위를 파악하지 않고, 경계에 특정 값을 넣어주는 것을 좋아한다. 이렇게 구현할 경우, 전처리 코드가 생기지만, 탐색하는 코드가 읽기 편하다는 장점이 있다.