4개의 정점을 가진 유향 그래프가 주어진다. 해당 그래프의 간선은 확률을 가지고 있으며, 한 정점에서 진출하는 간선의 확률의 합은 1이다. 이 확률은 '그녀'가 한 정점에서 다른 정점으로 이동할 확률이다.
임의의 출발점에서 시작해서 정해진 횟수만큼 '그녀'가 이동을 할 때, 마지막에 각 정점에 '그녀'가 있을 확률을 구해야 한다.
간단한 확률 문제이기 때문에 시뮬레이션을 돌리면 됩니다.
- 출발할 수 있는 정점이 4개이기 때문에, 0.25의 확률을 가지고 시작한다.
- 각 간선을 통해서 다른 정점으로 이동할 때마다 해당 간선의 확률을 곱해준다.
- 이동횟수가 제한에 도달한다면, 현재의 확률을 현재 정점의 확률 총합에 합해준다.
- 나머지 3개의 정점에서도 반복한다.
위의 과정은 DFS를 통해서 처리하였습니다. 재방문이 허용되기 때문에 visited 배열은 선언하지 않았고, 문제의 단위시간만큼 이동하면 return하는 식으로 코드를 작성하였습니다.
#include <bits/stdc++.h>
using namespace std;
int t, m;
double res[4];
vector<pair<int, double>> adj[4];
void dfs(int now, double p, int cnt)
{
if (cnt == t)
{
res[now] += p * 100;
return;
}
for (auto& i : adj[now])
dfs(i.first, p * i.second, cnt + 1);
}
int main(void)
{
cin >> t >> m;
while (m--)
{
char s, e;
double p;
cin >> s >> e >> p;
adj[s - 'A'].push_back({ e - 'A', p });
}
for (int i = 0; i < 4; i++)
dfs(i, 0.25, 0);
cout << fixed;
cout.precision(3);
for (int i = 0; i < 4; i++)
cout << res[i] << '\n';
return 0;
}