CrazyBot

문제

로봇은 n 번 움직이며, 각 단계에서 1방향 EWSN 를 랜덤하게 선택해서 한 칸 이동한다.

확률은 인자로 제공된다. (EWSN 순)

로봇이 같은 지점을 통과하지 않으면 성공일때,

성공적으로 보행할 확률을 리턴한다.

예시 입력

1, 25, 25, 25, 25

2, 25, 25, 25, 25

7, 50, 0, 0, 50

14, 50, 50, 0, 0

14, 25, 25, 25, 25

예시 출력

1
0.75
1
0.00012207
0.00884549

생각의 변화

데이터를 어떻게 표현하면 좋을까

매 조건마다 무엇이 바뀌여야 하는지
그리고 중복체크 방법에 대한 생각이 부재하기에 어렵다는 생각이 들었다

E다음 W면 중복, 순서를 기억해야 할까

좌표를 모두 기억해야 할까

n 이 1-14 이므로 지나온 모든 좌표를 기억해도 된다

기존 히스토리가 있으니 중복은 (탐색중에) 그자리에서 바로 알수 있다
별다른 기발한 방법이 아니라

이전단계 점화식 느낌이다

dfs(x,y,n)
= prob[0] x dfs(x+1, y, n-1) + prob[1] x dfs(x-1, y, n-1) + prob[2] x dfs(x, y-1, n-1) + prob[3] x dfs(x, y+1, n-1)

재귀를 쓰기에 식이 간결

덧셈이므로, 0 이면 무시

1이 나와야 윗 단계에서 확률곱이 가능

이전 경로 히스토리 update, 근데 이건 어디까지나 '가능성' 이므로
이 가능성이 끝나면 다시 돌려놓아야 할것

pseudo code

bool coord[100][100] = {false}
double prob[4]

getProbability(n, east, west, south, 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)
    
dfs(x, y, n)
    if coord[x][y] == true
        return 0

    if n == 0
        return 1
        
    coord[x][y] = true
    
    a1 = prob[0] * dfs(x+1, y, n-1)
    a2 = prob[1] * dfs(x-1, y, n-1)
    a3 = prob[2] * dfs(x, y-1, n-1)
    a4 = prob[3] * dfs(x, y+1, n-1)
    
    coord[x][y] = false
    
    return a1+a2+a3+a4;