algospot NUMB3RS

문제 링크입니다: 

물론 완전탐색 알고리즘을 사용한다면 쉽게 풀 문제이지만 동적 계획법을 사용하여 문제를 푸는 것이 실력 향상에는 도움이 될 것 같습니다.

여기서 중요한 포인트는 감옥에서 나온 날부터 시작하는 것이 아니라 찾고자 하는 마을, 즉 day일부터 거꾸로 답을 구하는 형식이라는 것입니다!

/*

위험한 살인마 두니발 박사가 감옥에서 탈출했다.

그는 다음과 같은 조건으로 도주를 한다.

1. 두니발 박사는 검문을 피해 산길로만 이동

2. 두니발 박사는 교도소를 탈출한 당일, 교도소와 인접한 마을 하나로 도망쳐 은신한다

3. 두니발 박사는 수색을 피하기 위해 매일 인접한 마을로 움직여 은신한다.

 

마을의 수, 탈출 후 지금까지 지난 일 수, 교도소가 있는 마을번호를 입력하고

마을 그래프를 입력한다.(2차원 행렬에 인접한 도시는 1, 그 외 0)

그 다음 찾고 싶은 마을 갯수를 입력 후 마을 번호를 해당 갯수만큼 입력한다.

입력한 마을번호에 은신하고 있을 확률을 출력하시오

*/

#include <iostream>

#include <vector>

#include <cstring> //memset

using namespace std;

 

int villageNum, day, jail, searchNum; //마을의 수, 탈출 후 일 수, 교도소 있는 번호, 찾고 싶은 마을의 수

int village[50][50]; //최대 50개 마을

int adjacent[50]; //adjacent[i]는 마을 i와 인접한 마을의 수

double cache[50][100]; //최대 50개 마을, 최대 100일

/*

//완전 탐색 알고리즘

double search(vector<int> &path)

{

        //기저 사례:day일이 지난 경우

        if (path.size() == day + 1)

        {

               //이 시나리오가 searchNum에서 끝나지 않는다면 무효

               if (path.back() != searchNum)

                       return 0.0;

               //path의 출현 확률 계산

               double result = 1.0;

               for (int i = 0; i < path.size(); i++)

                       result /= adjacent[path[i]]; //인접한 마을의 갯수만큼 나눠준다

               return result;

        }

        double result = 0.0;

        //경로의 다음 위치를 결정한다

        for (int there = 0; there < villageNum; there++)

        {

               if (village[path.back()][there])//인접했다면 추가

               {

                       path.push_back(there);

                       result += search(path);

                       path.pop_back();

               }

               return result;

        }

}

*/

 

//동적 계획법

double search(int here, int days) //here 해당 마을, days: 지난 일 수

{

        //기저 사례

        if (days == 0)

               return (here == jail ? 1.0 : 0.0); //시작은 감옥

        //메모이제이션

        double &result = cache[here][days];

        if (result != -1.0)

               return result;

        result = 0.0;

        //거꾸로 확률을 계산한다. 즉 해당 마을부터 시작(정방향이라면 감옥부터 시작)

        for (int there = 0; there < villageNum; there++)

               if (village[here][there]) //there와 인접해있다면

                       result += search(there, days - 1) / adjacent[there]; //∑(1/adjacent(there) * search(there, days-1));

        return result;

}

 

int main(void)

{

        int test_case;

        cin >> test_case;

        if (test_case < 1 || test_case>50)

               exit(-1);

       

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

        {

               cin >> villageNum >> day >> jail;

               if (villageNum < 2 || villageNum>50 || day < 1 || day>100 || jail < 0 || jail >= villageNum)

                       exit(-1);

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

                       for (int k = 0; k < villageNum; k++)

                              cin >> village[j][k];

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

                       for (int k = 0; k < 100; k++)

                              cache[j][k] = -1;

               memset(adjacent, 0, sizeof(adjacent));

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

                       for (int k = 0; k < villageNum; k++)

                              adjacent[j] += village[j][k]; //인접한 마을 갯수 초기화

 

               cin >> searchNum;

               if (searchNum > villageNum || searchNum < 1)

                       exit(-1);

               vector<int> v;

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

               {

                       int there;

                       cin >> there;

                       if (there<0 || there>villageNum-1)

                              exit(-1);

                       v.push_back(there);

               }

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

               {

                       cout.precision(8);

                       cout << search(v[j], day) << " ";

               }

               cout << endl << endl;

        }

        return 0;

}

개발환경:Visual Studio 2017

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

[참고] 프로그래밍 대회에서 배우는 알고리즘 문제해결전략