백준 1405번 미친 로봇

문제

통제 할 수 없는 미친 로봇이 평면위에 있다. 그리고 이 로봇은 N번의 행동을 취할 것이다.

각 행동에서 로봇은 4개의 방향 중에 하나를 임의로 선택한다. 그리고 그 방향으로 한 칸 이동한다.

로봇이 같은 곳을 한 번보다 많이 이동하지 않을 때, 로봇의 이동 경로가 단순하다고 한다. (로봇이 시작하는 위치가 처음 방문한 곳이다.) 로봇의 이동 경로가 단순할 확률을 구하는 프로그램을 작성하시오. 예를 들어, EENE와 ENW는 단순하지만, ENWS와 WWWWSNE는 단순하지 않다. (E는 동, W는 서, N은 북, S는 남)

입력

첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고,  모든 확률은 100보다 작거나 같은 자연수 또는 0이다. 그리고, 동서남북으로 이동할 확률을 모두 더하면 100이다.

출력

첫재 줄에 로봇의 이동 경로가 단순할 확률을 출력한다. 절대/상대 오차는 10-9 까지 허용한다.

 

 

 

 

진짜 너무 힘들었다..... 두가지를 놓쳤는데 

1) 좌표를 공유하면 안된다. 마지막 까지 이동 한 후에 돌아온다 해도 좌표에 대한 복구를 안해줬기 때문에 첫번째 경로는 온전한 DFS가 된다고 하더라도 두번째부터 첫번째의 마지막 경로에서 시작하는 불상사가 일어남.

2) direction 확률을 곱해주고 다시 나눠주는 작업은 DFS(Back Tracking)에 부합하는데 중요한건 확률이 0일수도 있다는 점.... 따라서 0이 나눠지는 불상사가 일어남.

 

작은 실수로는 자료형을 신경안쓰고 소수점 출력이 안되는 걸 보고 읭? 했지만 이건 뭐... 금방 고쳤다.

 

마지막으로 소수점 10자리까지 출력해야 하는데

c++에서는 cout <<fixed; 를 통해서 소수점 위치를 고정 시킨 후에

cout.precision(10); 하면 소수점 밑으로 10자리까지 출력하겠다고 선언한다. fixed없이 precision 호출하면 정수부도 포함하므로 주의!

 

 

 

 

#include <iostream>


using namespace std;

int count;
double direction[4];


double total ;
double curr = 1.0;

int checkpoint;

int arr[30][30];




void DFS(int x, int y, int start,double f)
{

    if(start == count )
    {
    
   total += f;
   return;
    
}
arr[x][y] = true;
    
   for(int i = 0; i<4; i++)
   {
         

 
 if(i == 0)
 {
  int nextx = x+1;
  int nexty = y;
  
  if(!arr[nextx][nexty] )
  {
   
  
  
          DFS(nextx,nexty,start+1,f*direction[i]);
          arr[nextx][nexty] = false;
          }
 }
 else if(i==1)
 {
 
  int nextx = x-1;
  int nexty = y;
  if(!arr[nextx][nexty] )
  {
  
   
  
          DFS(nextx,nexty,start+1,f*direction[i]);
          arr[nextx][nexty] = false;
          }
 }
 else if(i==2)
 { 
 
  int nextx = x;
  int nexty = y-1;
  if(!arr[nextx][nexty] )
  {
  
  
   
    
          DFS(nextx,nexty,start+1,f*direction[i]);
          arr[nextx][nexty] = false;
          }
 }
 else if(i ==3)
 {
   int nextx = x;
  int nexty = y+1;
  if(!arr[nextx][nexty] )
  {
  
  
  
   
          DFS(nextx,nexty,start+1,f*direction[i]);
          arr[nextx][nexty] = false;
         }
 }

         
         
        



        
         
   }


}

int main(void)
{

cin >> count ;

for(int i = 0; i<30; i++)
 {
  for(int j = 0; j<30; j++)
  arr[i][j] = 0;
 }


for(int i =0; i<4; i++)
{
cin >> direction[i];
direction[i] /= 100;
}



DFS(15,15,0,1.0);



cout << fixed;
    cout.precision(10);
 cout << total<< "\n";

        return 0;



}