[C++] 백준 16502번: 그녀를 찾아서

be_clever·2022년 1월 21일
0

Baekjoon Online Judge

목록 보기
40/172

문제 링크

16502번: 그녀를 찾아서

문제 요약

4개의 정점을 가진 유향 그래프가 주어진다. 해당 그래프의 간선은 확률을 가지고 있으며, 한 정점에서 진출하는 간선의 확률의 합은 1이다. 이 확률은 '그녀'가 한 정점에서 다른 정점으로 이동할 확률이다.
임의의 출발점에서 시작해서 정해진 횟수만큼 '그녀'가 이동을 할 때, 마지막에 각 정점에 '그녀'가 있을 확률을 구해야 한다.

접근 방법

간단한 확률 문제이기 때문에 시뮬레이션을 돌리면 됩니다.

  1. 출발할 수 있는 정점이 4개이기 때문에, 0.25의 확률을 가지고 시작한다.
  2. 각 간선을 통해서 다른 정점으로 이동할 때마다 해당 간선의 확률을 곱해준다.
  3. 이동횟수가 제한에 도달한다면, 현재의 확률을 현재 정점의 확률 총합에 합해준다.
  4. 나머지 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;
}
profile
똑똑해지고 싶어요

0개의 댓글