[Algospot] 두니발 박사의 탈옥 (문제 ID : NUMBE3RS)

문제

위험한 살인마 두니발 박사가 감옥에서 탈출했습니다. 수배지를 붙이고 군경이 24시간 그를 추적하고 있지만 용의주도한 두니발 박사는 쉽사리 잡히지 않았습니다. d일이 지난 후에야 경찰은 프로그래밍의 천재인 찰리 교수)를 찾아왔습니다. 찰리 교수는 두니발 박사가 감옥에 남겨둔 노트를 분석해 다음과 같은 가설을 세웠습니다.

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

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

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

이 가설을 검증하기 위해 교도소로부터 산길로 연결된 n 개 마을들의 지도를 위 그림과 같이 구했습니다. 두니발 박사가 이 가설에 맞춰 행동하고, 움직일 수 있는 마을이 여러 개 있을 경우 그 중의 하나를 임의로 선택한다고 합시다. d 일 후에 두니발 교수가 각 마을에 있을 확률을 계산하는 프로그램을 작성하세요.

예를 들어 위 지도에서 3번 마을에 교도소가 있다고 합시다. 탈옥 직후 두니발 교수는 0번, 1번, 2번, 4번, 5번 중의 한 도시를 임의로 골라 도망칩니다. 따라서 1일 후에 두니발 교수가 0번 마을에 숨어 있을 확률은 1/5이고, 2일 후에 1번 마을에 숨어 있을 확률은 1/15입니다.

입력

입력의 첫 줄에는 테스트 케이스의 수 c (1 <= c <= 50) 가 주어집니다. 그 후 각 줄에 지도에 포함된 마을의 수 n (2 <= n <= 50) 과 탈출 후 지금까지 지난 일수 d (1 <= d <= 100), 그리고 교도소가 있는 마을의 번호 p (0 <= p < n) 가 주어집니다. 마을은 0번부터 n-1 번까지 순서대로 번호가 매겨져 있습니다. 그 후 n 줄에는 각각 n 개의 정수로 행렬 A 가 주어집니다. i 번 행의 j 번 숫자 A[i][j] 가 1인 경우 i 번 마을에서 j 번 마을을 잇는 산길이 있다는 것을 의미하며, 0인 경우 길이 없다는 것을 의미합니다. 그 다음 줄에 확률을 계산할 마을의 수 t (1 <= t <= n) 가 주어지고, 그 다음 줄에 t 개의 정수로 확률을 계산할 마을의 번호 q (0 <= q < n) 가 주어집니다.

한 마을에서 다른 마을로 길이 있으면 반대 방향으로도 항상 있으며, 한 마을에서 자기 자신으로 연결되는 길은 없다고 가정해도 좋습니다.

출력

각 테스트 케이스마다 t 개의 실수로 각 마을에 두니발 박사가 숨어 있을 확률을 출력합니다. 10-7 이하의 절대/상대 오차가 있는 경우 정답으로 처리됩니다.

---

쉽게 보고 까불었다가 시간초과로 혼났다. 생각해보면 완전탐색으로 풀었으니 시간초과가 뜨는게 당연하다. 그 방식으로라도 답은 맞았음에 만족하지만 더 발전하기위해 노력해보자.

이 문제는 일단 입력값도 많고 생각할 요소가 곳곳에 숨어있어 까다롭다. 일단 맵에 대한 정보를 2차원 배열 A에 모두 저장하고 만약 두 도시가 연결되어있다면 1차원 배열 link의 값을 1 늘린다. A[i][j]==1일때 link[i]나 link[j] 둘 중 하나만 1을 증가하면 된다. 결국 모든 정보를 받아오기 때문이다. 이걸 간과하고 link[i]++, link[j]++을 했다가 확률이 절반으로 줄었다. 아무튼 그 후엔 박사가 숨어있을 마을을 입력 받고 그 마을에 있을 확률을 계산한다. 확률 계산은 0일째부터 d일까지 증가하는 방식으로 검색하는 방법이 있고, d일부터 거꾸로 검사하는 방식이 있다. 전자는 모든 경로를 검색한 후에 d일째 마을이 q번 마을일 때에만 정답인 경우이므로 사실상 모든 경로를 검색하는 꼴이지만 후자는 q번 마을부터 역으로 올라가 마지막 0일째에 p번 마을에 있으면 정답이므로 시간이 더 절약된다. 따라서 후자 방식으로 풀어보자면 cal(village, day)는 탈옥 후 day일째에 박사가 village번 마을에 숨어있을 확률이다. 확률 계산을 위해 dp배열은 double형식으로 해야한다. 기저사례를 보면 0일째에 p번 마을에 있을때만 1.0 (100%)를 반환한다. 그 후 0번부터 N번 마을중에서 연결이 된 마을에만 재귀적으로 조사를하며 link[i]를 나눈다. i번 마을에 있을 확률에서 i번 마을과 연결된 마을 수를 나눠야 village번 마을에 도달할 확률이기 때문이다. link[i]를 나눠야 하는지 link[village]를 나눠야 하는지를 유의해서 풀어야한다.

 

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/Algospot/NUMB3RS.cpp

chosh95/STUDY

C++ 코드

#include <iostream>
#include <cstring>
using namespace std;
int A[51][51];
int link[51];
double dp[51][101];
int C, N, d, p, t, q;

//day일째에 village마을에서 도망치는 확률
double cal(int village, int day)
{
	if (day == 0) return (village == p ? 1.0 : 0.0);
	double& res = dp[village][day];
	if (res != -1.0) return res;
	res = 0.0;
	for (int i = 0; i < N; i++) {
		if (A[village][i]) {
			res += cal(i,day-1) / link[i];
		}
	}
	return res;
}


int main()
{
	cin >> C;
	while (C--) {
		cin >> N >> d >> p;
		memset(A, 0, sizeof(A));
		memset(link, 0, sizeof(link));
		for (int i = 0; i < N; i++) {
			for (int j = 0; j <= d; j++) {
				dp[i][j] = -1.0;
			}
		}
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				cin >> A[i][j];
				if (A[i][j] == 1) {
					link[i]++;
				}
			}
		}
		cin >> t;
		while (t--) {
			cin >> q;
			cout.precision(8);
			cout << cal(q,d) << " ";
		}
		cout << endl;
	}
}