Algorithm/Baekjoon

[Algorithm] Baekjoon 1405번 : 미친 로봇

MaxLevel 2022. 10. 13. 15:26

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

 

1405번: 미친 로봇

첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고,  모든 확률은 100보다 작거나 같은 자

www.acmicpc.net

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
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;
 
}
 cs

 

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

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