BOJ 2066 카드놀이

카드놀이

(https://www.acmicpc.net/problem/2066)

어떤 상태까지 도달할 확률이 \(p\)이고, 이 상태에서 고를 수 있는 방법이 \(N\)개가 있다면, 다음 상태로 넘어갈 확률은 \(\frac{p}{N}\)다.

문제는 구현하는 방법이다. 상태는 카드가 그룹별로 \(0\)개부터 \(4\)개까지 있을 수 있으니 \(5^9\)개가 있는데, 모든 상태를 확인하면서 또 DP처럼 구하려면 순서가 중요하니 9중 반복문을 써야한다.

하지만 그러면 코드가 복잡해지니, 남은 카드의 수의 합은 항상 순서가 있다는 점에서 BFS로 구현했다.

상태도 9차원 배열로 만들어두면 코드가 복잡해지니 map을 사용했다.

#include <bits/stdc++.h>
 
using namespace std;
 
char num[9][5], shp[9][4];
map<vector<int>, double> p;
 
int main() {
    for (int i = 0;i < 9;++i)
        for (int j = 3;j >= 0;--j)
            scanf(" %c %c", &num[i][j], &shp[i][j]);
    num[0][4] = 'a';
    for (int i = 1;i < 9;++i)
        num[i][4] = num[i - 1][4] + 1;
 
    p[{ 0, 0, 0, 0, 0, 0, 0, 0, 0 }] = 1;
    
    queue<vector<int> > q;
    q.push({ 0, 0, 0, 0, 0, 0, 0, 0, 0 });
    while (!q.empty()) {
        vector<int> now = q.front();
        q.pop();
        
        int cnt = 0;
        for (int i = 0;i < 9;++i)
            for (int j = i + 1;j < 9;++j)
                if (num[i][now[i]] == num[j][now[j]])
                    cnt++;
 
        for (int i = 0;i < 9;++i)
            for (int j = i + 1;j < 9;++j)
                if (num[i][now[i]] == num[j][now[j]]) {
                    vector<int> nxt = now;
                    nxt[i]++;
                    nxt[j]++;
 
                    if (!p.count(nxt))
                        q.push(nxt);
                    p[nxt] += p[now] / cnt;
                }
    }
 
    printf("%.10lf", p[{ 4, 4, 4, 4, 4, 4, 4, 4, 4 }]);
 
    return 0;
}