#1405 미친 로봇(Full Search, Back Tracking)

이번 문제는 경로를 다니면서, 지나온 길을 거치지 않을 확률을 계산하는 것입니다.  난이도 Gold V로 어렵지는 않은 문제이고요.  복잡한 알고리즘이 아니라, 단순한 백트랙킹을 구현하면 됩니다.

 

동서남북으로 움직일 수 있는 확률이 주어지고, 동서남북으로 확률적으로 N칸 움직였을 때, 지나온 경로를 다시 방문하지 않는 경로로 움직일 확률이 얼마일까를 계산하는 문제입니다.

 

예를 들어서 로봇이 NESW로 순차적으로 움직였다면, 원위치로 돌아왔으니, 지나온 경로를 지나게 됩니다.  NNES 라던지, SWWS 와 같은 경로는 4칸을 움직이면서 지나온 경로를 지나지 않는 움직임이 됩니다.

 

Mad Robot

 

문제를 풀기 위해서는 BFS, DFS 들 중 어떤 것을 사용하든 상관이 없습니다.  전 편한 DFS를 사용했습니다.  최대 움직임은 14로 제한되어 있고, 각각 4방향으로 움직이지만, 실제로 중간에 지나온 경로로 오면 거치지 않으므로 시간이 넉넉하지는 않지만 가능은 합니다.  물론 평균적인 시간이긴 하겠지만, 제 풀이는 24ms가 나왔습니다.  방문여부만 잘 검사한다면, 문제를 통과하는데에는 어려움이 없을겁니다.

 

아래는 제가 작성한 소스입니다.  소스는 참고용으로 봐주세요.

//----------------------------------------------------------
//  baekjoon #1405 - Mad Robot
//    - by Aubrey Choi
//    - created at 2020-01-01
//----------------------------------------------------------
#include <stdio.h>

int n, p[4], d[4]={1,-1,30,-30};
char v[900];
double dfs(int c, int k, double cp)
{
  if(c==n) return cp;
  v[k]=1;
  double s=0;
  for(int i=0;i<4;i++)
  {
    if(v[k+d[i]]) continue;
    s+=dfs(c+1, k+d[i], cp*p[i]/100);
  }
  v[k]=0;
  return s;
}
int main()
{
  scanf("%d%d%d%d%d",&n,p,p+1,p+2,p+3);
  printf("%.10lg\n", dfs(0, 465, 1));
}