💡 백트래킹/브루트포스 알고리즘/깊이 우선 탐색/그래프 이론/그래프 탐색/수학/확률론
Memory 1116KB Time 28ms Code Length 743B
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
#include<stdio.h>
double percent[4];
int time = 0;
double result = 0;
int visited[30][30] = {0};
int dy[] = {0,0,-1,1};
int dx[] = {1,-1,0,0};
void dfs(int node, int y, int x, double p) {
if (node == time) {
result += p;
return;
}
for (int i = 0; i < 4; i++) {
if (percent[i] == 0)continue;
int ny = y + dy[i];
int nx = x + dx[i];
if (visited[ny][nx]) continue;
visited[ny][nx] = 1;
dfs(node + 1, ny, nx, p*percent[i]);
visited[ny][nx] = 0;
}
}
int main()
{
// 동, 서, 남, 북
double Input[4];
scanf("%d %lf %lf %lf %lf", &time, &Input[0], &Input[1], &Input[2], &Input[3]);
for (int i = 0; i < 4; i++) {
percent[i] = Input[i] / 100;
}
visited[15][15] = 1;
dfs(0, 15,15, 1);
printf("%0.18f", result);
}
이 코드는 30x30 크기의 격자에서 주어진 시간(time) 동안 이동할 때, 각 방향으로 이동할 확률이 주어졌을 때 최종적으로 특정 위치에 도달할 확률을 계산하는 프로그램이다.
- dfs 함수는 재귀적으로 각 방향으로 이동하며 각 위치에서의 확률을 계산한다. 만약 주어진 시간에 도달하면 결과에 해당 확률을 더하고 반환한다.
- main 함수에서는 입력을 받고, 주어진 확률을 계산하여 시작 위치에서 dfs 함수를 호출한다.
- 결과는 최종적으로 도달한 확률을 출력한다.
