두니발 박사의 탈옥
문제
두니발 박사가 감옥에서 탈출했다. d일이 지난 후에야 경찰은 찰리 교수를 찾아왔고 찰리 교수는 다음과 같은 가설을 세웠다.
두니발 박사는 산길로만 이동한다.
교도소를 탈출한 당일, 교도소와 인접한 마을 하나로 도망쳐 은신한다.
수색을 피하기 위해 매일 인접한 마을로 움직여 은신한다.
n개의 마을들의 지도가 다음과 같을때 임의의 마을을 선택한다고 가정하면, d일 후에 두니발 교수가 마을에 있을 확률을 계산하는 프로그램을 작성하시오.
입력
첫 줄에는 테스트 케이스의 수c(1~50)가 주어진다.
그 후 각 줄에 지도에 포함된 마을의 수 n(2~50), 탈출 후 지금까지 지난 일 수 d(1~100), 교도소가 있는 마을 번호 p(0~n)이 주어진다.
그 후 n줄에는 각각 n개의 정수로 행렬 A가 주어진다.
그다음 줄에 확률을 계산할 마을의 수 t(1~n)이 주어진다.
마지막으로 t개의 정수로 확률을 계산할 마을의 번호 q가 주어진다.
예제 입력 및 출력
입력
2
5 2 0
0 1 1 1 0
1 0 0 0 1
1 0 0 0 0
1 0 0 0 0
0 1 0 0 0
3
0 2 4
8 2 3
0 1 1 1 0 0 0 0
1 0 0 1 0 0 0 0
1 0 0 1 0 0 0 0
1 1 1 0 1 1 0 0
0 0 0 1 0 0 1 1
0 0 0 1 0 0 0 1
0 0 0 0 1 0 0 0
0 0 0 0 1 1 0 0
4
3 1 2 6
출력
0.83333333 0.00000000 0.16666667
0.43333333 0.06666667 0.06666667 0.06666667
소스 코드
#include <iostream>
using namespace std;
int Case;
double cache[50][50][100];
class Escape {
private:
int** map; //마을 연결관계
int town; //마을의 수
int day; //지난 일수
int prison; //교도소 마을 번호
int count; //확률을 계산할 마을의 수
int* counttown; //확률을 계산할 마을의 번호
double street[50]; //연결된 도로수 저장하는 배열
public:
void Input() {
//마을의 수, 경과일수, 감옥이있는 마을 입력
cin >> town >> day >> prison;
//2차원 배열 생성
map = new int*[town];
for (int i = 0; i < town; i++)
map[i] = new int[town];
memset(street, 0.0, sizeof(street)); //연결된 도로 수 0으로 초기화
//배열 입력 받기
for (int i = 0; i < town; i++) {
for (int j = 0; j < town; j++) {
cin >> map[i][j];
if (map[i][j] == 1) //연결되어있으면
street[i]++; //도로수+1
}
}
//확률읠 계산할 마을의 수 입력
cin >> count;
counttown = new int[count];
// 마을 번호 입력
for (int i = 0; i < count; i++)
cin >> counttown[i];
}
int getCount() {
return count;
}
int getCounttown(int i) {
return counttown[i];
}
int getPrison() {
return prison;
}
int getDay() {
return day;
}
double findDoc(int depart, int arrive, int day) {
//이미 계산된 값 반환
if (cache[depart][arrive][day] != 0.0)
return cache[depart][arrive][day];
//함수의 마지막 탈출조건 - 앞으로 한번 이동 가능할때 -> 연결되어있으면 확률을구하고 연결안되어있으면 0을 반환
if(day==1){
//연결된 길이 없다면
if (map[depart][arrive] == 0)
return cache[depart][arrive][1] = 0.0; //갈 확률 = 0
//연결된 길이 있다면
else
return cache[depart][arrive][1] = 1 / street[depart]; //갈 확률 = 1/연결된 도로 수
}
//점화식 - day가 2 이상 남았을때 -> 재귀호출
for (int i = 0; i < town; i++) {
//depart-i 가 연결되어있다면
if (map[depart][i] == 1)
//A = 현재 depart에서 다음 i로 가는 확률 : 1/street[depart]
//B = 다음 i에서 arrive로 가는 확률 : findDoc(i,arrive,day-1)
//C = 현재 depart에서 arrive까지 갈 수 있는 모든 경로의 확률의 합
//C= for(A*B)
cache[depart][arrive][day] += (1 / street[depart]) * findDoc(i, arrive, day - 1); //
}
return cache[depart][arrive][day];
}
};
Escape* escape;
int main(void) {
cin >> Case;
escape = new Escape[Case];
for (int i = 0; i < Case; i++)
escape[i].Input();
int prison, arrive, day;
for (int i = 0; i < Case; i++) {
//Case별 캐시 초기화
memset(cache, 0, sizeof(cache));
//결과 출력
for (int j = 0; j < escape[i].getCount(); j++) {
prison = escape[i].getPrison();
arrive = escape[i].getCounttown(j);
day = escape[i].getDay();
cout << escape[i].findDoc(prison, arrive, day) << " ";
}
cout << endl;
}
}
문제 풀이
1. 문제 해결 전략
-
감옥이 있는 마을에서 목적지까지 갈 확률을 모두 구하고 더해준다 (or연산)
-
현재 마을에서 목적지까지의 확률 구하기 : 현재 마을에서 다음 마을로 갈 확률 x 다음 마을에서 목적지까지 갈 확률
-> 1/street[depart] x findDoc(다음마을, 목적지, day-1)
-> 다음 마을은 연결되어있는 모든 마을을 반복문으로 순회하여 재귀 함수를 호출한다.
-> 재귀 함수의 반환 값은 기존 확률에 곱하여 준다 (and 연산)
-
ex) 0번 마을을 출발하여 2일 후 0번 마을로 올 확률 -> (a) x(a) + (b) x(b) + (d) x(d) = 1/3 x 1 + 1/3 x 1/2 + 1/3 x 1
2. cache값 설정
-
cache[depart][arrive][day] : depart번 마을에서 출발하여 arrive번 마을까지 day일에 걸쳐서 갈 확률
3. 기저 사례
-
cache값이 이미 계산되었으면 바로 반환
4. 함수 탈출 조건
-
day가 1일 때 현재 마을에서 목적지 마을에 연결되어있지 않다면 확률은 0 이므로 0 반환 연결되어 있으면 현재 마을에서 목적지 마을로 갈 확률을 계산하여 반환
5. 점화식
-
cache[depart][arrive][day] += (현재 마을에서 다음 마을 갈 확률) * findDoc(다음 마을, 목적지 마을, day-1) -> 연결된 모든 마을을 순회하여 확률을 구하고 더해준다.