8.16 문제 : 두니발 박사의 탈옥(Python) - 마르코프 연쇄

문제 출처 : algospot.com :: NUMB3RS

algospot.com :: NUMB3RS

---

1. 완전 탐색에서 시작하기

(1) 알고리즘 설계

• 감옥이 있는 마을 p에서 시작해 마을 q까지 가는 길이가 d+1인 경로를 모두 생성한다.
• p에서 시작해 d번 인접한 마을로 옮기는 모든 경로를 생성하고, 이 중 q에서 끝나는 경로들이 출현할 확률을 계산하여 그 합을 반환한다.
• search(path) = path로 시작하는 모든 경로를 모두 만들고, 그 중 q에서 끝나는 것들의 출현 확률의 합을 반환

(2) 코드 - 풀이 해설 방법

1) 문제 입력(출력은 구현 안함)

for tc in range(int(input())):
    n, d, p = map(int, input().split())

    connected = [] # 전체 마을 연결 정보를 저장
    degree = [0] * n # i번 마을에 대해 인접해 있는 마을의 수 저장
    for i in range(n):
        connected.append(list(map(int, input().split())))
        for j in range(n):
            if connected[i][j] == 1:
                degree[i] += 1

    t = int(input())
    qs = list(map(int, input().split()))

• 각 마을에 연결된 다른 마을의 수를 degree 리스트에 미리 계산해 담아둔 것에 유의!

2) search(path)

# 완전 탐색으로 구현
# search(path) : path로 시작하는 모든 경로를 다 만들고 이 중 q에서 끝나는 것들의 출현 확률의 합을 계산
def search(path):
    # 기저 사례 : d일이 경과
    # path의 크기가 d+1이면 인덱스 d를 검사 -> d번째 날 박사의 위치
    if len(path) == d+1:
        # 경로가 q에서 끝나지 않는다면 무효
        if path[-1] != q:
            return 0.0

        # 경로가 q에서 끝날 때 해당 경로가 나올 단일 확률 계산
        result = 1.0
        for i in range(len(path)-1):
            result /= degree[path[i]]

        return result

    # 만들 수 있는 모든 경로들을 생성
    for next in range(n):
        if connected[path[-1]][next] == 1:
            path.append(next)

            result += search(path) # 위 기저 사례에서 경로가 q에서 끝나는 단일 확률들의 합을 통해 전체 확률을 계산
            
            path.pop()

    return result

---

2. 메모이제이션

(1) 알고리즘 설계

• 완전 탐색에서 메모이제이션으로 변경하기 위해 지금까지 배운 대로, 이전에 선택한 조각들에 대한 정보를 가능한 한 최소한도로 줄일 필요가 있다.
• 완전 탐색에서 search()에 전달되는 path 매개변수가 쓰이는 용도는 크게 세 가지이다.
• 1. path의 마지막 원소 : 현재 위치를 의미하고 다음 이동할 마을을 결정할 때 필요하다.
• 2. path의 길이 : 탈옥 후 지난 날짜를 의미하며 경로가 끝났는지 판별할 때 필요하다.
• 3. 확률 계산 : 경로가 완성되었을 때 출현 확률을 계산하기 위해 필요하다.

 

• 최소한의 정보만 남기기 위해서 다음과 같이 변화를 적용한다.
• 1. path 대신 현재 위치를 의미하는 here와 탈옥 후 경과한 날짜 days를 재귀 호출에 전달한다.
• 2. 전체 경로의 확률을 계산하는 것이 아니라, 현재 위치에서 시작해 남은 날짜 동안 움직여 q에 도달할 확률을 계산한다.
• 결과적으로 다음과 같은 부분 문제 정의를 얻을 수 있다.
• search2(here, days) = 두니발 박사가 days일째에 here번 마을에 숨어 있을 때, 마지막 날에 q번 마을에 있을 조건부 확률을 반환한다.

 

• 현재 있는 마을 here에서 연결된 마을의 집합을 adj(here)이라고 할 때, 다음이 성립한다.

(2) 조건부 확률

• 동적 계획법에서 재귀 함수는 '앞으로 선택하는 조각들의 결과만을 반환해야 한다.'
• 이는 확률을 구할 때도 똑같이 적용되는데 어떤 경로 A={a0, a1, ... , ad}가 출현할 확률 P(A)는 다음과 같이 계산할 수 있다.

• 이때, search2()에 경우 각 경로에 대해 다음 값들로 나타낼 수 있다.

• 어떤 경로에 대해서 위 계산으로 나타나는 값들을 합하면 search2()가 반환하는 값을 알 수 있다.
• 이 값들은 P(A)를 구성하는 식들의 뒷부분으로 '앞으로 선택하는 조각들의 결과만을 반환해야 한다.'는 원칙에 맞는다.

(3) 코드 - 풀이 해설 방법

1) 문제 입-출력

for tc in range(int(input())):
    n, d, p = map(int, input().split())

    connected = [] # 전체 마을 연결 정보를 저장
    degree = [0] * n # i번 마을에 대해 인접해 있는 마을의 수 저장
    for i in range(n):
        connected.append(list(map(int, input().split())))
        for j in range(n):
            if connected[i][j] == 1:
                degree[i] += 1

    t = int(input())
    qs = list(map(int, input().split()))

    # search2()
    for q in qs:
        cache = [[-1] * d for _ in range(n)] # q가 바뀔때 마다 새롭게 cache를 갱신해야 함

        if q == qs[-1]:
            print(search2(p, 0))
        else:
            print(search2(p, 0), end=" ")

• q에 대해서 매번 새롭게 cache를 갱신해야 하는 것에 유의해야 한다!
• 교도소가 있는 마을 p부터 목적지인 q마을까지의 경로를 탐색하기 때문에 함수의 인수로 p와 0을 사용한다.

2) search2(here, days)

# 메모이제이션으로 구현
# search2(here, days) : days일째 here번 마을에 숨어 있을 때, 마지막 날 q번 마을에 있을 조건부 확률
# nd의 부분 문제를 갖고 각각 n 시간에 해결하므로 전체 시간 복잡도는 O(n^2d)
# 그러나 테스트 케이스 t개가 존재 하므로 총 O(n^2dt)
def search2(here, days):
    # 기저 사례 : d일이 경과
    if days == d:
        # d일째(마지막 날) q번 마을에서 d일째(마지막 날) q번 마을에 있을 확률은 1
        # d일째(마지막 날) 다른 마을에서 d일째(마지막 날) q번 마을에 있을 확률은 0
        return 1.0 if here == q else 0.0

    # 메모이제이션
    # cache[here][days] : days일 째 here번 마을에서 계속 이동을 진행할 때 d일째(마지막 날) q번 마을에 도착할 확률을 저장
    if cache[here][days] > -0.5:
        return cache[here][days]

    cache[here][days] = 0.0
    for next in range(n):
        if connected[here][next]:
            # degree[here]로 나누눈 이유? 다음 날 next로 갈 확률을 의미
            cache[here][days] += search2(next, days+1) / degree[here]

    return cache[here][days]

• 도시 하나 당 부분 문제의 수는 n*d 이고 각각 문제를 해결하는데 n의 시간이 소요되므로 시간 복잡도는 O(d*n^2)이다.
• 그러나 테스트 케이스 t개가 존재하므로 테스트 케이스 하나에 걸리는 시간은 총 O(d*t*n^2)이다.

---

3. 반대 방향에서 풀기

(1) 부분 문제 재정의

• 계산의 순서를 반대 방향으로 바꾸어 구현하면 search2()보다 빠르게 구현할 수 있다.
• search2()에서는 항상 시작 지점부터 경로를 만들어 가며 d일째의 기저 사례에 q에 다다르는 경우를 찾았다.
• 그러나 q가 바뀌면 모든 문제의 답이 바뀔 수 밖에 없다.
• 이 문제로 인해 search2()의 문제 입-출력 단계에서 q에 대해 항상 cache를 갱신해야만 했다.
• 접근을 바꾸어 경로의 마지막인 q부터 경로를 만들어 가면 문제가 훨씬 수월해진다.(나는 사실 둘 다 어렵다..)

 

• search3(here, days) = 탈옥 후 days일째에 두니발 박사가 here번 마을에 숨어있을 확률
• search2(here, days)에 비하면 문제 정의가 훠어얼씬 직관적이다.
• 박사가 전날 prev에 있다가 오늘 here로 올 확률은 search(prev, days-1)에 1/|adj(prev)|를 곱한 값이다.
• 따라서 search3()를 다음과 같은 점화식으로 정의할 수 있다.

• 이렇게 부분 문제의 정의를 바꾼 덕분에 q가 바뀔때마다 모든 값을 재계산할 필요가 없으며 한 테스트 케이스당 시간 복잡도를 O(d*n^2)로 줄일 수 있다.

(2) 코드 - 풀이 해설 방법

1) 문제 입-출력

for tc in range(int(input())):
    n, d, p = map(int, input().split())

    connected = [] # 전체 마을 연결 정보를 저장
    degree = [0] * n # i번 마을에 대해 인접해 있는 마을의 수 저장
    for i in range(n):
        connected.append(list(map(int, input().split())))
        for j in range(n):
            if connected[i][j] == 1:
                degree[i] += 1

    t = int(input())
    qs = list(map(int, input().split()))

    # search3()
    cache = [[-1] * (d+1) for _ in range(n)] # q에 대해서 새롭게 cache를 갱신할 필요 없음!

    for q in qs:
        if q == qs[-1]:
            print(search3(q, d))
        else:
            print(search3(q, d), end=" ")

• search2()와 달리 q에 대해 새롭게 cache를 갱신할 필요가 없다.
• 경로를 목적지인 q부터 교도소가 있는 p까지 역으로 탐색하므로 함수의 인수를 문제의 목적지인 q와 마지막 날을 의미하는 변수 d의 값을 사용한다.

2) search3(here, days)

# 테스트 케이스 t에 구애받지 않는 O(n^2d) 알고리즘
# q부터 해서 역으로 계산하는 방법
# search3(here, days) : 탈옥 후 days일째에 박사가 here번 마을에 숨어있을 확률
def search3(here, days):
    # 기저 사례 : 0일째
    # 0번째 날 p번 마을에서 0번째 날 p번 마을에 있을 확률은 1
    # 0번째 날 다른 마을에서 0번째 날 p번 마을에 있을 확률은 0
    if days == 0:
        return 1.0 if here == p else 0.0

    # 메모이제이션
    # cache[here][days] : days일 째 here번 마을에 박사가 숨어있을 확률을 저장
    if cache[here][days] > -0.5:
        return cache[here][days]

    cache[here][days] = 0.0
    for prev in range(n):
        if connected[prev][here]:
            # degree[prev]로 나누눈 이유? 전날 prev에서 here로 올 확률을 의미
            cache[here][days] += search3(prev, days-1) / degree[prev]

    return cache[here][days]

• 경로가 역순으로 계산되기 때문에 함수 내 하단에 위치한 반복문 안의 조건문인 if connected[prev][here] 모습이 search2()와 다름에 유의해야 한다.

---

4. 마르코프 연쇄(Markov-Chain)

• 이 문제에서 다루는 마을들은 다음과 같은 성질을 갖고 있기 때문에 마르코프 연쇄라고 부르는 모델로 표현할 수 있다.

 

• 유한개의 상태가 존재한다.
• 매 시간마다 상태가 변경된다.
• 어떤 상태 a에서 다른 상태 b로 옮겨갈 확률은 현재 상태 a에 의해서만 좌우된다.
• a 이전에 어느 상태에 있었는지, 현재 시간은 얼마인지 등은 영향을 주지 않는다.

 

• 다음 단원인 9장에서 문제 해결을 위해 마르코프 연쇄를 이용하는 몇 가지 사용 예시들을 확인할 수 있다.

---

5. 후기

  확률에 대해서 동적 계획법을 적용하는 첫번째 문제이다. 3월 말쯤에 이 문제를 처음 접하고 지금에서야 다시 복습하는 개념으로 책을 다시 읽어보니 처음 공부했을 때 보다는 확실히 이해가 잘 되었다. 그래도 아마 다른 비슷한 문제에 대해서 이를 응용하는 단계까지는 아직 멀었다는 생각이 든다. 그래도 처음에는 진짜 이해도 안가고 그냥 무작정 따라쓰기하는 느낌이었는데 이제는 코드가 어떤식으로 문제 분석과 알고리즘 설계 과정을 따라갔는지 정도는 이해가 된다.

  생각해보면 책의 설명에서 단어나 변수명 같은게 직관적이지 못했다. 이를 개인적으로 이해하기 쉬운 형태로 바꾸었는데 책에서는 search2()의 다음 날 마을의 이름과 search3()에서 이전 날 마을의 이름을 동일하게 there로 사용했다. 나는 이를 각각 next와 prev로 바꿔서 이해했더니 한결 이해가기가 편했다. 그 외에도 책에선 날짜의 경과를 n으로 사용한다던지 하는 부분에서 마을의 수를 의미하는 n과 혼동이 일어날 가능성이 있어서 나는 이를 d로 표현한 것도 있다.

  현재 이 글을 포스팅하는 시점에서 9장 내용을 1/3정도 진행했는데, 9장에서 나오는 마르코프 연쇄에 관련한 문제에 비하면 이 문제는 정말 선녀같이 느껴진다. 이 책을 공부하면서 대충 이번년 상반기에는 책을 마무리하고 본격적으로 코딩 테스트 지원을 해볼까 생각하는데 이런 난이도와 진행 속도로 보면 과연 올해 하반기에도 가능할까 하는 걱정이 든다...

---

github : Algorithmic_Problem_Soving_Strategies/q7_0.py at main · LeeSeok-Jun/Algorithmic_Problem_Soving_Strategies (github.com)

LeeSeok-Jun/Algorithmic_Problem_Soving_Strategies