[C++] 백준 BOJ 1405번 미친 로봇

로봇이 이동하는 모든 경로를 다 돌아보면서 그 경로가 단순한 경로일때만 그 경로가 나올 확률을 계산해서 더해주면된다. 

로봇이 이동하는 경로의 수는 $$4^N (N=14일때 약 2.6억)$$ 이라서 시간초과가 날 것 같지만, 

방금 왔던 방향과 반대방향으로 가게되면 바로 단순경로가 아닌셈이 되므로, 사실상 $$3^N (N=14일때 약 5백만)$$ 개의 경로에 대해서만 확률을 계산하면 된다. 

 

#include <iostream>
using namespace std;
int N, east, west, south, north;
double possibility[4];
int dx[4]={0, 1, 0, -1};
int dy[4]={-1, 0, 1, 0};
bool movingArea[29][29];
double pos;
//move=지금까지의 이동횟수, curPos=현재까지 오는 경로의 확률, curX, curY=현재 로봇의 좌표
void bruteForce(int move, double curPos, int curX, int curY){
    if(move==N){ //단순 경로일때만 확률을 계산 
        pos+=curPos;
        return;
    }
    for(int i=0;i<4;i++){
        int nextX=curX+dx[i], nextY=curY+dy[i];
        if(movingArea[nextX][nextY]) //단순 경로가 아니라면 더 이상 볼 필요가 없다.
            continue;
        movingArea[nextX][nextY]=true;
        bruteForce(move+1, curPos*possibility[i], nextX, nextY);
        movingArea[nextX][nextY]=false;
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cout.precision(10);
    cout<<fixed; //출력 자리수 넉넉하게 잡기
    
    cin>>N>>east>>west>>south>>north;
    possibility[2]=east/100.0;
    possibility[0]=west/100.0;
    possibility[1]=south/100.0;
    possibility[3]=north/100.0;
    int startX=14, startY=14;
    movingArea[startX][startY]=true;
    bruteForce(0, 1, startX, startY);
    cout<<pos;
    return 0;
}

문제에서 절대/상대 오차는 10^(-9)까지 허용하므로 출력할 때 소수점 9자리 이상 출력할수 있도록 해야한다.

(따로 설정 안해주면 바로 오답처리...)

총 시간복잡도  $$3^N$$으로 해결