백준 1520번 내리막 길

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

미로 문제를 풀어본적 있다면 쉽게 풀 수 있는 문제입니다.

#include <iostream>

#include <cstring> //memset

using namespace std;

 

int map[500][500];

int cache[500][500];

//int cnt = 0; //경우의 수

int M, N; //세로의 크기, 가로의 크기

 

bool inRange(int y, int x) //범위 내에 있는지 확인

{

        return y >= 0 && y < M&&x >= 0 && x < N;

}

 

bool downHill(int y1, int x1, int y2, int x2) //내리막길인지 확인

{

        return map[y1][x1] > map[y2][x2];

}

 

//시간 초과 소스

/*

void search(int y, int x)

{

        if (y == M - 1 && x == N - 1)

        {

               cnt++;

               return;

        }

        if (inRange(y + 1, x) && downHill(y, x, y + 1, x))

               search(y + 1, x);

        if (inRange(y, x - 1) && downHill(y, x, y, x - 1))

               search(y, x - 1);

        if (inRange(y, x + 1) && downHill(y, x, y, x + 1))

               search(y, x + 1);

}

*/

 

//메모이제이션 사용

int search(int y, int x)

{

        if (y == M - 1 && x == N - 1)

               return 1;

        int &result = cache[y][x];

        if (result != -1)

               return result;

        result = 0;

        if (inRange(y - 1, x) && downHill(y, x, y - 1, x)) //위

               result += search(y - 1, x);

        if (inRange(y + 1, x) && downHill(y, x, y + 1, x)) //아래

               result += search(y + 1, x);

        if (inRange(y, x - 1) && downHill(y, x, y, x - 1)) //왼쪽

               result += search(y, x - 1);

        if (inRange(y, x + 1) && downHill(y, x, y, x + 1)) //오른쪽

               result += search(y, x + 1);

        return result;

}

 

int main(void)

{

        cin >> M >> N;

        for (int i = 0; i < M; i++)

               for (int j = 0; j < N; j++)

                       cin >> map[i][j];

        memset(cache, -1, sizeof(cache));

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

        return 0;

}

 

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~