[c++] BOJ 1520 :: 내리막길

난이도 : 골드 4

걸린 시간 : 1시간 반 이상

 

문제

문제 바로가기

 

풀이

• 우선 완전탐색으로 해당 문제를 생각해본다.
• 완전탐색으로 구현한다면 dfs를 사용해서 재귀로 구현할 것이다.
• 재귀의 매개변수(받는 정보)는 현재 위치일 것이고, 내보내는 정보는 현재 위치에서 마지막까지의 경로의 수일 것이다.
• (0,0)을 처음으로 재귀함수에 넘기면 (0,0)에서 끝까지의 경로의 수이므로 우리가 원하는 답이 나온다.
• 재귀는 위, 오른쪽, 아래, 왼쪽으로 접한 부분으로 옮겨가며 해당 장소의 경로의 수를 현재 장소의 경로의 수에 더하는 방식으로 진행된다.
  • 이 때, 장소는 맵 안에 있어야한다.
  • 이 때, 내리막길로만 갈 수 있으므로 현재보다 더 높은 수를 가진 장소는 제외이다.
• 이렇게 구성하면 갔던 곳을 또 가는 경우가 생기므로 DP를 이용한다.
• 재귀함수의 return 조건
  • 재귀함수 초반에 memo된 경로의 수가 있다면 해당 경로의 수를 넘겨준다.
  • 재귀함수 초반에 현재 위치가 끝(M-1, N-1)이라면 1을 넘겨준다.

 

코드

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

int M, N;
int arr[500][500];
int memo[500][500];
// 오 => 아 => 왼 => 위
int direction[4][2] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };

bool isThereBad(int r, int c) {
    // 맵 안에 있는지 확인
    return (r < 0 || c < 0 || r >= M || c >= N);
}

int returnPathNum(int r, int c) {
    if (memo[r][c] != -1)
        return memo[r][c];
    memo[r][c] = 0;
    for (int i = 0; i < 4; i++) {
        int row = r + direction[i][0];
        int col = c + direction[i][1];
        if (isThereBad(row, col))
            continue;
        if (arr[r][c] <= arr[row][col])
            continue;
        // 내리막일 때
        memo[r][c] += returnPathNum(row, col);
    }
    return memo[r][c];
}

int main() {
    // 생각의 흐름
    // 완전 탐색으로 구성한다면, 최단 경로가 아니므로 dfs 고려
    // 재귀로 구현할테고 재귀함수에서 DP로 return해줄 수 있게 구현
    // 재귀로 구현하면 받는 정보는 현재 위치, 내보내는 정보는 현재 위치에서 가질 수 있는 경로의 값
    // 현재 위치에서 목적지까지 갈 수 있는 경로의 갯수 = 주위의 낮은 곳으로부터 오는 경로의 합
    // 빠져나가는 조건 : M-1, N-1 일 때 1
    // memo 되어있을 때 memo값
    // memo는 경로의 갯수를 구하고 나서 표시

    // 입력 받기
    cin >> M >> N;
    for (int i = 0; i < M; i++) { // 10^5
        for (int j = 0; j < N; j++) {
            cin >> arr[i][j];
        }
    }
    memset(memo, -1, sizeof(memo));

    memo[M - 1][N - 1] = 1;
    cout << returnPathNum(0, 0);
}

• 주의할 것
  • memset을 이용하려면 cstring 라이브러리를 import 해야한다.

결과