[Code SASA] 정독실에서 tic-tac-toe

https://code.sasa.hs.kr/problem.php?id=1067

SASA OJ

 

하루를 성공적으로 시작하게 해준 문제!!!

 

1. Tip => 코딩 문제 풀 때는 Pomotroid를 애용하자. 25분 코딩 - 5분 휴식 루틴!

 

2. 확률 계산이 중요한 문제. 처음에 turn에 따라 확률 계산을 다르게 해야하는 줄 알고 멘붕이 왔었다. 그런데 사실 turn은 그저 맵의 상태를 바꾸어주는 것일 뿐 실제로 돌을 두는 판단을 해야되는 시점은 오직 맨 처음 뿐이므로 쉽게 쉽게 재귀적으로 확률을 계산해주면 된다.

 

3. 흑돌이 이겼으면 => 확률 1 , 백돌이 이겼으면 => 확률 0, 

그 누구도 이기지 않았으면 => (각각의 지점에 돌을 놓았을 떄의 확률 합) / (돌을 놀 수 있는 곳의 개수)

 

백트래킹으로도 제한 시간 내에 풀린다. 메모이제이션까지 하니 0ms로 통과했다.

//you should actually read the stuff at the bottom
//howtoliveworldnice.tistory.com
#include<bits/stdc++.h>
#define pb push_back
#define vsort(v) sort(v.begin(),v.end())
#define fastIO ios::sync_with_stdio(false);cin.tie(0);
const int INF = 1e9;
using namespace std;
int arr[3][3];
double DT[20000],eps=1e-15;
inline int state(int mp[][3]){
    for(int i=0;i<3;i++){
        if(arr[i][0]==arr[i][1]&&arr[i][1]==arr[i][2])
            return arr[i][0];
        if(arr[0][i]==arr[1][i]&&arr[1][i]==arr[2][i])
            return arr[0][i];
    }
    if(arr[0][0]==arr[1][1] && arr[1][1]==arr[2][2])
        return arr[1][1];
    if(arr[2][0]==arr[1][1] && arr[1][1]==arr[0][2])
        return arr[1][1];
    return 0;
}
inline void itom(int k,int mp[][3]){
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++){
            mp[i][j]=k%3;
            k/=3;
        }
}
inline void mtoi(int&k,int mp[][3]){
    k=0; int w=1;
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++){
            k+=mp[i][j]*w;
            w*=3;
        }
}
double prob(int mp[][3],int turn){
    int k;
    mtoi(k,mp);
    if(DT[k]-(-1.0)>eps) return DT[k];
    int chk=state(mp);
    if(chk!=0) return DT[k]=(chk==1?1.0:0.0);
    int cnt=0;
    double sum=0;
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            if(mp[i][j]!=0) continue;
            ++cnt;
            mp[i][j]=turn;
            sum+=prob(mp,3-turn);
            mp[i][j]=0;
        }
    }
    if(cnt==0) return 0;
    return DT[k]=sum/cnt;
}
void solve(int mp[][3]){
    int r=2,c=2;
    double ans=-1.0;
    for(int j=2;j>=0;j--)
        for(int i=2;i>=0;i--){
            if(mp[i][j]!=0) continue;
            mp[i][j]=1;
            double p=prob(mp,2);
            if(p-ans>eps){
                r=i; c=j;
                ans=p;
            }
            mp[i][j]=0;
        }
    mp[r][c]=1;
}
void print(int mp[][3]){
    for(int i=0;i<3;i++,cout<<'\n')
        for(int j=0;j<3;j++)
             cout<<mp[i][j]<<' ';
}
int main(){
    fastIO; fill(&DT[0],&DT[20000],-1.0);
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
             cin>>arr[i][j];
    solve(arr);
    print(arr);
}
 
/* stuff you should look at for
    * int overflow, array bounds
    * sepcial cases (n=1?)
    * do smth instead of nothing and stay organized
    * WRITE STUFF DOWN
    idea by Benq
*/