[Topcoder] CrazyBot(미친 로봇)

통제 불능의 로봇이 평면에 올려지고, 그것은 무작위적인 단계를 밟는다.
각 단계에서 로봇은 네 방향 중 하나를 무작위로 선택하고 해당 방향으로 한 단위를 이동합니다.
로봇이 북쪽, 남쪽, 동쪽 또는 서쪽을 선택할 확률은 각각 북쪽, 남쪽, 동쪽 및 서쪽 퍼센트입니다.

로봇이 동일한 지점을 두 번 이상 방문하지 않는 경우 로봇의 경로는 단순한 것으로 간주됩니다. (로봇의 시작 지점은 항상 처음 방문한 지점입니다.) 로봇의 경로가 단순할 확률이 포함된 double를 반환합니다. 예를 들어, "EEN"과 "ENW"는 단순하지만, "ENWS"와 "WWWSNE"는 아니다. ('E', 'W', 'N', 'S'는 각각 동서남북을 나타낸다.)\

Definition

Class:

 

CrazyBot

Method:

 

getProbability

Parameters:

 

int, int, int, int, int

Returns:

 

double

Method signature:

 

double getProbability(int n, int east, int west, int south, int north)

(be sure your method is public)

Constraints

- n will be between 1 and 14, inclusive.

- east will be between 0 and 100, inclusive.

- west will be between 0 and 100, inclusive.

- south will be between 0 and 100, inclusive.

- north will be between 0 and 100, inclusive.

- The sum of east, west, south and north will be 100.

Examples

0)

1

25

25

25

25

Returns: 1.0

The robot only takes one step, so it never visits a point more than once.

1)

2

25

25

25

25

Returns: 0.75

The robot will visit its starting point twice only if the two moves are in opposite directions.

2)

7

50

0

0

50

Returns: 1.0

Here, the only possible directions are north and east, so the robot will never visit the same point twice.

3)

14

50

50

0

0

Returns: 1.220703125E-4

Here, the only possible directions are east and west. The only two available paths are "EEEEEEEEEEEEEE" and "WWWWWWWWWWWWWW". The probability is equal to 2 / (2^14).

4)

14

25

25

25

25

Returns: 0.008845493197441101

The probability is quite small for n=14.

---

전형적인 깊이우선탐색(dfs) 문제이다.

 

전체 이동 경로 케이스를 찾고, 성공한 케이스만을 추려내서 이를 확률로 계산한다. 

 

경로가 실패할 경우 더이상 해당 경로의 트리를 탐색하는 것을 중지하고 다른 경로를 탐색한다. (가지치기)

 

bool grid[100][100] = {false};
int vx[] = {1, -1, 0, 0};
int vy[] = {0, 0, 1, -1};
double prob[4];

평면을 100 * 100의 plane으로 설정한다. false는 아직 탐색하지 않는 지점이다. 

 

동, 서, 남, 북의 이동을 표현하기 위해 vx, vy를 선언하였다. 

 

그리고 각 방향의 확률을 위해 prob 배열을 선언하였다. 

 

class CrazyBot
{
public:
    double getProbability(int n, int east, int west, int south, int north){
        prob[0] = east/100.0;
        prob[1] = west/100.0;
        prob[2] = south/100.0;
        prob[3] = north/100.0;
        
        return dfs(50, 50, n);
    }

전체 이동 횟수인 n과 각 방향의 이동확률(%)을 인자로 받는다. 

 

그리고 dfs로 이동 경로를 탐색하고 성공 확률을 계산한다. 

    double dfs(int x, int y, int n){
        if(grid[x][y]) return 0;
        if(n == 0) return 1;
        
        grid[x][y] = true;
        double ret = 0;
        for(int i=0; i<4; i++){
            ret += dfs(x+vx[i], y+vy[i], n-1)*prob[i];
        }
        grid[x][y] = false;
        
        return ret;
    }

dfs의 전체 코드이다. 

        if(grid[x][y]) return 0;
        if(n == 0) return 1;

탐색하는 x, y가 이미 방문한 지점(true)일 경우 0을 반환하여 해당 경로의 탐색을 종료한다. 

 

그리고 n==0일 경우 마지막 leaf 노드까지 순회하였으므로 1을 반환하여 위로 거슬러 올라간다. 

        grid[x][y] = true;
        double ret = 0;
        for(int i=0; i<4; i++){
            ret += dfs(x+vx[i], y+vy[i], n-1)*prob[i];
        }

dfs의 진행은 방문 지점(x, y)를 true로 설정하고, 각 방향마다 더 깊은 dfs를 수행한다.

 

n에서 1을 빼서 이동 횟수를 차감한다. 

 

dfs가 최종 반환하는 결과는 0 혹은 1이므로 이를 전체 확률로 구하기 위해 prob 를 곱하여 

 

누적 확률을 계산한다.

        grid[x][y] = false;

dfs의 마지막 노드까지 탐색하고 거슬러 올라갈 때 다시 거슬러가는 지점마다 false로 바꿔주는데, 

 

한 경로의 탐색이 다른 경로의 탐색에 영향을 미치면 안되므로 이러한 조치를 하는 것이다. 

 

        return ret;

최종 ret을 반환한다.