[Algorithm] Baekjoon 1405번 : 미친 로봇

https://www.acmicpc.net/problem/1405

1405번: 미친 로봇

int visitedMap[29][29] = { false };
vector<int> pv; // 동서남북
vector<vector<int>> dir = { {0,1}, {0,-1}, {1,0}, {-1,0} }; // 동서남북
int targetCount = 0;
double sum = 0.0f;
 
void DFS(double p, int y, int x, int count)
{
    if (count == targetCount)
    {
        sum += p;
        return;
    }
 
    for (int i = 0; i < pv.size(); i++)
    {
        if (pv[i] == 0) continue; // 확률 0%면 넘어가기
 
        int nextY = y + dir[i][0];
        int nextX = x + dir[i][1];
 
        if (visitedMap[nextY][nextX]) continue; // 방문한적있으면 넘어가기.
        if (nextY < 0 || nextY >= 29) continue;
        if (nextX < 0 || nextX >= 29) continue;
        
        visitedMap[nextY][nextX] = true;
        DFS(p * pv[i] / 100.0f, nextY, nextX, count + 1);
 
        visitedMap[nextY][nextX] = false; // 흔적지우기
    }
}
 
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int n = 0;
    int temp = 0;
 
    cin >> n;
    targetCount = n;
 
    if (n == 1)
    {
        cout << 1.0f;
        return 0;
    }
 
    for (int i = 0; i < 4; i++)
    {
        cin >> temp;
        pv.push_back(temp);
    }
 
    visitedMap[14][14] = true;
    DFS(1.0f, 14, 14, 0);
 
    cout.precision(10);
    cout << sum;
 
}

 

처음 봤을 때 문제랑 예제가 살짝 이해가 안됐던 문제..

그냥 n번의 이동을 마쳤을 때의 확률을 누적해서 출력하면 된다.