[BaekJoon] 1520 내리막 길 :: monton

문제

https://www.acmicpc.net/problem/1520

풀이

이 문제를 처음 보았을 땐 간단한 DFS 문제인줄 알았다

하지만 dfs로는 시간초과가 날 수 밖에없다 따라서 dfs+dp 문제이다

1. 일단 visit 체크 배열을 -1로 모두 초기화 해준다

2. 함수 func에서 2-1) x좌표와 y좌표가 범위를 넘어서는지 체크해준다

     2-2) 내리막길이 아니면 지나갈 수 없는 길이므로 0을 반환해 준다

     2-3) 목표 지점에 도착하면 1을 반환

     2-4) 만약 visit 값이 -1이 아니면 visit값 반환 (x,y 좌표에서 있는 경로의 갯수 반환을 의미)

     2-5) 4방향으로 2-1,2-2,2-3,2-4를 계속 반복하면서 모든 visit값을 저장해준다

dp는 아직 개념이 잡히지 않은 나에게는 정말 어렵다 ㅠㅠ

다시 한번 공부해 보아야할 부분인 것 같다

맨 아래는 단순 dfs로 풀었을 때이고 두번째는 dp를 잘 못풀어서 시간 초과가 났다

코드

#include <iostream>
using namespace std;
 
int N, M;
int arr[501][501], visit[501][501];
int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };
 
int func(int x, int y, int num) {
 
    if (x < 0 || y<0 || x >= N || y >= M) return 0;
    if (num <= arr[x][y]) return 0;
    if (x == N - 1 && y == M - 1) return 1;
    if (visit[x][y]!=-1) return visit[x][y];
 
    visit[x][y] = 0;
    for (int i = 0; i < 4; i++) {
            visit[x][y] += func(x + dir[i][0], y + dir[i][1], arr[x][y]);
    }
 
    return visit[x][y];
}
 
int main() {
    cin >> N >> M;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> arr[i][j];
            visit[i][j] = -1;
        }
    }
 
    cout << func(0, 0, 10001);
}