C++로 방향 그래프의 모든 노드 제거에 필요한 기대 연산 횟수 계산하기

문제 개요

방향 그래프 G의 인접 행렬이 주어져 있다고 가정해 보겠습니다. 그래프가 완전히 비워질 때까지 다음 연산을 반복해서 수행합니다. 그래프에서 정점 하나를 선택하면, 그 정점과 함께 해당 정점에서 간선을 따라 도달할 수 있는 모든 정점이 제거됩니다. 정점이 제거되면 그 정점에 연결된 간선 역시 함께 삭제됩니다. 이때 구해야 하는 값은 이 연산이 수행되는 횟수의 기댓값입니다.

예를 들어 위 그래프에서 정점 A를 가장 먼저 선택하면 나머지 정점까지 한 번에 제거되므로 연산은 1회로 끝납니다. 반면 B를 먼저 선택하면 B와 C가 제거되고, 두 번째 연산에서 A를 제거해야 하므로 총 2회가 필요합니다. C를 먼저 선택하는 경우도 마찬가지로 2회입니다. 따라서 평균은 (1 + 2 + 2) / 3 = 1.6667이 됩니다.

핵심 아이디어

이 문제는 기댓값의 선형성(linearity of expectation)을 이용하면 깔끔하게 해결할 수 있습니다. 연산 횟수는 곧 "직접 선택되어 제거된 정점의 개수"와 같습니다.

정점 i가 직접 선택되려면, i 자신을 포함해 i에 도달할 수 있는 정점들의 집합 S_i 안에서 i가 가장 먼저 선택되어야 합니다. 그 이유는 S_i에 속한 다른 정점이 먼저 선택되는 순간 i도 함께 제거되어 버리기 때문입니다. |S_i| = k라고 할 때, 어떤 정점이 먼저 선택될지는 모두 동등한 확률을 가지므로 i가 직접 선택될 확률은 1/k입니다. 따라서 전체 기대 연산 횟수는 모든 정점에 대해 1/k를 더한 값, 즉 Σ 1/k가 됩니다.

알고리즘 단계

위 아이디어를 구현하기 위해 다음 단계를 따릅니다.

1. 도달 가능 행렬 초기화: n := G의 크기로 설정하고, 모든 i에 대해 G[i][i] := 1로 만듭니다(자기 자신에게 도달 가능하다고 표시).
2. 전이 폐쇄(transitive closure) 계산: Floyd-Warshall 방식으로 삼중 반복문을 수행하며, G[i][k]와 G[k][j]가 모두 0이 아니면 G[i][j] := 1로 갱신합니다. 완료되면 G[i][j]는 "i에서 j로 도달 가능한지"를 나타냅니다.
3. 기댓값 누적: 각 정점 i에 대해 G[j][i]가 0이 아닌 j의 개수 k(즉, i에 도달할 수 있는 정점의 수, i 포함)를 세고, ans := ans + 1.0 / k를 누적합니다.
4. ans를 반환합니다.

n := size of G
for initialize i := 0, when i < n, update (increase i by 1), do:
    G[i, i] := 1
for initialize k := 0, when k < n, update (increase k by 1), do:
   for initialize i := 0, when i < n, update (increase i by 1), do:
      for initialize j := 0, when j < n, update (increase j by 1), do:
         if G[i, k] is non-zero and G[k, j] is non-zero, then:
            G[i, j] := 1
ans := 0
for initialize i := 0, when i < n, update (increase i by 1), do:
   k := 0
   for initialize j := 0, when j < n, update (increase j by 1), do:
      if G[j, i] is non-zero, then:
         (increase k by 1)
   ans := ans + 1.0 / k
return ans

C++ 구현 예제

더 나은 이해를 위해 다음 구현을 살펴보겠습니다.

#include <bits/stdc++.h>
using namespace std;

double solve(vector<vector<int>> G){
    int n = G.size();
    // 자기 자신으로의 도달 가능 표시
    for (int i = 0; i < n; ++i)
       G[i][i] = 1;
    // Floyd-Warshall 방식으로 전이 폐쇄 계산
    for (int k = 0; k < n; ++k)
       for (int i = 0; i < n; ++i)
          for (int j = 0; j < n; ++j)
             if (G[i][k] && G[k][j])
                G[i][j] = 1;
    double ans = 0;
    for (int i = 0; i < n; ++i){
       int k = 0;
       for (int j = 0; j < n; ++j)
          if (G[j][i])
             ++k;  // 정점 i에 도달할 수 있는 정점의 수
       ans += 1.0 / k;
    }
    return ans;
}
int main(){
    vector<vector<int>> G = { { 0, 1, 0 }, { 0, 0, 1 }, { 0, 1, 0 }};
    cout << solve(G) << endl;
}

입력

{ { 0, 1, 0 }, { 0, 0, 1 }, { 0, 1, 0 } }

출력

1.66667

복잡도 분석

전이 폐쇄 계산에 O(n³), 기댓값 합산에 O(n²)이 소요되므로 전체 시간 복잡도는 O(n³)입니다. 공간 복잡도는 인접 행렬을 저장하는 데 필요한 O(n²)입니다.