알고리즘 - markov 문제

n = 5
d = 2
start = 0
connected = [
    [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]
]

deg = [3, 2, 1, 1, 1]

# v 마을에 있을 때, days일이 지난 후 t 마을에 탈옥수가 있을 확률
def solve(v, days):
    # base case
    if days == d:
        # 아래 재귀함수 코드에 따라 solve(v, days)는 solve(0,0)부터 시작해서 인접한 마을(i마을)로 이동 시, days + 1을 해주었기 때문에 실제 days일이 지난 후, v마을에 있는 확률이 된다. 
        # 고로, d == days 일 때, v마을이 t마을에 있다면 1.0, 없다면 0.0이 된다.
        return 1.0 if v==t else 0.0

    # 이미 계산된 값이 cache에 있다면 그 값을 반환
    if cache[v][days] != None:
        return cache[v][days]

    # 반환값을 계산해서 반환
    cache[v][days] = 0.0
    for i in range(n):
        # v마을에서 i마을로 한번에 갈 수 있는 경우(connected[v][i] == 1)
        if connected[v][i]:
            # v마을에서 i마을로 한번에 갈 경우 1일이 소요되며, v마을에서 한번에 갈 수 있는 마을 중에 i마을을 가는 경우이므로, solve(i, days+1) / deg[v] 가 v마을에서 i마을로 갈 수 있는 확률이 된다.
            # v마을에서 한번에 갈 수 있는 모든 마을에서의 특정 일수가 지난 후, 탈옥수가 있을 확률을 더하여 반환한다.(base case에 의해, d 값에 따라 경우의 수는 달라지게 된다.)
            cache[v][days] += solve(i, days+1)/deg[v]
    return cache[v][days]

if __name__ == "__main__":
    prob = []
    # v마을에서 d일 지난 후, t마을에 있을 확률(t = 0, 1, 2, 3, 4)
    for t in range(n):
        cache = [[None for _ in range(30)] for _ in range(10)]
        prob.append(solve(0, 0))
    # prob = [2일 지난 후, 0번 마을에 있을 확률, 2일 지난 후, 1번 마을에 있을 확률, ..., 2일 지난 후, 4번 마을에 있을 확률]
    print(prob)