문제
https://www.acmicpc.net/problem/1405
문제해설
로봇이 동서남북 방향으로 움직인다.
로봇이 총 이동할 수 있는 횟수와
각 방향으로 움직일 수 있는 확률이 주어진다.
이 때 로봇의 이동경로가 단순할 확률을 구하면 된다.
이동경로가 단순하다는 것에 대한 설명을 참 어렵게 써놨다.
일부러 이렇게 해서 난이도를 높이는건지…
아무튼 로봇이 한번 방문한 곳은 다시 방문하지 않도록 이동할 확률을 구하면된다.
문제풀이
dfs를 이용해 해결했다.
로봇이 한방향으로 최대 14번 이동할 수 있기 때문에
배열은 넉넉히 30X30으로 잡고
시작지점은 (15,15)로 설정했다.
이 문제에서 주의할 점은 우선 동서남북 방향이다.
동서남북 순서대로 입력이 들어오는데
자기마음대로 받으면 나중에 고생하게된다.
그리고 방문체크 한 것을 재귀가 끝나면서 다시 풀어줘야 한다.
그래야지 모든 경우의 수가 파악된다.
마지막으로는 소수점 9자리까지 출력을 해줘야한다.
c++ 같은 경우는
1
2
cout.precision(10);
cout << fixed << 출력할변수;
이렇게 하면 총 10자리를 출력해주기 때문에 위와같이 처리하면 된다.
전체코드
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
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef pair<int, int>P;
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };
double dir[4];
int visited[30][30];
int n;
double res;
void dfs(P now, double pro) {
int x = now.first;
int y = now.second;
if (visited[x][y] == n + 1) {
res += pro;
return;
}
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (visited[nx][ny])
continue;
visited[nx][ny] = visited[x][y] + 1;
dfs({ nx,ny }, pro * dir[i]);
visited[nx][ny] = 0;
}
}
int main() {
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> n;
for (int i = 0; i < 4; i++) {
double x; cin >> x;
dir[i] = x / 100;
}
visited[15][15] = 1;
dfs(P(15, 15), 1.0);
cout.precision(10);
cout << fixed << res;
return 0;
}