알고리즘 문제해결 전략

Ch.8.16 문제 ID NUMB3RS

종만북

8.16 문제: 두니발 박사의 탈옥 ( 문제ID : NUMB3RS, 난이도: 중)

문제 분류 : 동적계획법(메모리제이션)
문제의 예제 케이스도 틀렸습니다.
모든 확률 문제는 경우의 수로 풀 수 있다고 생각하여, 경우의 수로만 구하려다 보니 어디가 문제인지 찾지 못하였습니다.
아래의 순서를 따라가면 글쓴이의 의도를 파악할 수 있습니다.
완전탐색으로 먼저 접근한 후, 이를 메모이제이션으로 변경하기 위해 일련의 과정을 거칩니다.
- 조각을 구성하기 위해 과거 + 미래 관련 데이터를 미래 관련 데이터로만 변경하려 합니다.
한니발이 어떤 지점을 기점으로 연결된 다른 지점들로 이동할때는 [원래지점에서의 확률/연결된 지점 수] 를 한 확률이 각 인접 지역에 전달됩니다.

역시 완전탐색에서 시작하자

감옥이 있는 마을 p에서 시작해서 마을 q까지 가는 길이 n+1인 경로들을 모두 생성하는 작업은 완전 탐색의 전매특허입니다.

p에서 시작해 n번 인접합 마을로 옮기는 모든 경로를 생성하고, 이 중 q에서 끝나는 것들이 출현할 확률을 계산해 그들의 합을 반환합니다.

int n, d, p , q;
// connected[i][j]= 마을 i,j가 연결되어 있나 여부
// deg[i] = 마을 i와 연결된 마을의 개수
int connected[51][51], deg[51];
double search(vector<int>& path){
    // 기저 사례: d일이 지난 경우
    if(path.size() == d+1){
        // 이 시나리오가 q에서 끝나지 않는다면 무효
        if(path.back() != q)return 0.0;
        // path의 출현 확률을 계산한다
        double ret = 1.0;
        for(int i = 0; i + 1 < path.size(); ++i)
            ret /= deg[path[i]];
        return ret;
    }
    double ret = 0;
    // 경로의 다음 위치를 결정한다.
    for(int there = 0; there < n; there++)
        if(connected[path.back()][there]){
            path.push_back(there);
            ret += search(path);
            path.pop_back();
        }
    return ret;
}

메모이제이션

물론 이대로는 메모이제이션을 할 수 없습니다.
지금까지 풀었던 문제들에서 배운 대로, 이전에 선택한 조각들에 대한 정보를 가능한 한 최소한도로 줄일 필요가 있습니다.

search()에 전달되는 path 변수의 용도 3가지

path의 마지막 원소는 현재 위치: 다음 마을을 결정할 때 필요합니다.

path의 길이는 탈옥 후 지난 날짜: 경로가 끝났는지 알 때 필요합니다.

확률계산: 완성된 경로의 출현 확률을 계산할 때 필요합니다.

우리는 나머지 조각들을 해결하는 데 필요한 최소의 정보만 남기고 나머지를 없애는 연습을 해본적이 있습니다. 다음과 같은 변화를 적용하면 됩니다.

path 대신 현재 위치 here와 탈옥 후 지난 날짜 days를 재귀 호출에 전달합니다.

전체 경로의 확률을 계산하는 것이 아니라, 현재 위치에서 시작해서 남은 날짜 동안 움직여 q에 도달할 확률을 계산합니다.

search2(here, days) = 두니발 박사가 days일째에 here번 마을에 숨어 있을 때, 마지막 날에 q번 마을에
                      있을 조건부 확률을 반환한다.

O(nd)개의 부분 문제를 갖고 각각을 O(n)시간에 해결하므로, 전체 시간 복잡도는 O(n^2d)가 됩니다.
if(ret > -0.5 ) 로 초기화 여부를 판단하는 점도 일종의 테크닉이라고 생각합니다.

int n, d, p , q;
// cache[][]는 -1로 초기화해 둔다.
double cache[51][101];
// connected[i][j]= 마을 i,j가 연결되어 있나 여부
// deg[i] = 마을 i와 연결된 마을의 개수
int connected[51][51], deg[51];
// days일째에 here번 마을에 숨어 있다고 가정하고,
// 마지막 날에 q번 마을에 숨어 있을 조건부 확률을 반환한다.
double search2(int here, int days){
    // 기저 사례: d일이 지난 경우
    if(days == d)return (here == q ? 1.0 : 0.0);
    // 메모이제이션
    double& ret = cache[here][days];
    if(ret > -0.5)return ret;
    ret = 0.0;
    for(int there = 0; there < n; there++)
        if(connected[here][there])
            ret += search2(there, days+1) / deg[here];
    return ret;
}

반대방향에서 풀기

search2의 경우 O(n^2d)의 복잡도는 도시 하나당 걸리는 시간입니다.
따라서 테스트 케이스 하나에 걸리는 시간은 사실 O(n^2dt)가 됩니다.
하지만 search3 처럼 구현하면 q가 바뀔때마다 모든 값을 재계산 할 필요가 없고, 따라서 한 테스트 케이스당 시간 복잡도를 O(n^2d)로 줄일 수 있습니다.
search2의 경우, 두니발 박사가 도망갈 수 있는 경로들을 항상 시작부터 만들어 나가며, d일째의 기저 사례에 q에 다다르는 경우를 찾았습니다.
그러니 q가 바뀌면 모든 문제의 답이 바뀔 수밖에 없습니다.
반면 접근을 바꿔서 경로의 반대쪽 끝(q)부터 경로를 만들어 나가면 문제가 훨씬 쉬워집니다.
이 부분 문제의 정의는 다음과 같이 바뀝니다.

search3(here, days) = 탈옥 후 days일째에 두니발 박사가 here번 마을에 숨어 있을 확률

double search3(int here, int days){
    // 기저 사례: 0일째
    if(days == 0) return (here == p ? 1.0 : 0.0);
    // 메모이제이션
    double& ret = cache[here][days];
    if(ret > -0.5)return ret;
    ret = 0.0;
    for(int there=0; there < n; there++)
        if(connected[here][there])
            ret += search3(there, days-1) / deg[there];
    return ret;
}