반응형
문제 출처 :
https://www.acmicpc.net/problem/1405
알고리즘 분석 :
문제 해결에 필요한 사항
1. DFS / BFS
개인적으로 문제를 제대로 이해하지 못하고 헤매던 문제이다.
이 문제는 결국 무얼 의미하냐면 visit배열이 있을 때
visit배열을 중복해서 방문하지 않는 모든 확률을 구하라는 의미이다.
즉, 1,2에 왔다가 동서남북 4개 방향 중 어떤 방향으로 이동하다가 나중에 다시 1,2에 오면 안된다는것이다.
문제가 매우 간단하고, 4^14이지만 DFS로 해결할 수 있는 이유는 단순하지 않은 경로가 매우 많기에 가능하다.
visit 배열을 visit[29][29]로두어 1~28의 y,x 위치를 표현했고, 처음 시작은 가장 중앙점인 14,14부터 시작하는 것으로 하였다.
소스 코드 :
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 | #include <iostream> #include <cstdio> using namespace std; int n; int nE, nW, nS, nN; bool visit[29][29]; double ans; void dfs(int y, int x, int cnt, double total) { visit[y][x] = true; if (cnt == n) ans += total; if (cnt < n && !visit[y - 1][x]) dfs(y - 1, x, cnt + 1, total * nN / 100); if (cnt < n && !visit[y + 1][x]) dfs(y + 1, x, cnt + 1, total * nS / 100); if (cnt < n && !visit[y][x - 1]) dfs(y, x - 1, cnt + 1, total * nW / 100); if (cnt < n && !visit[y][x + 1]) dfs(y, x + 1, cnt + 1, total * nE / 100); visit[y][x] = false; } int main() { scanf("%d", &n); scanf("%d %d %d %d", &nE, &nW, &nS, &nN); dfs(14, 14, 0, 1.0); printf("%.10lf", ans); return 0; } // This source code Copyright belongs to Crocus // If you want to see more? click here >> | Crocus |
반응형
'Applied > 알고리즘 문제풀이' 카테고리의 다른 글
[14002번] 가장 긴 증가하는 부분 수열 4 (0) | 2017.03.22 |
---|---|
[1298번] 노트북의 주인을 찾아서 (2) | 2017.03.22 |
[2225번] 합분해 (0) | 2017.03.20 |
[10942번] 팰린드롬? (0) | 2017.03.19 |
[1325번] 효율적인 해킹 (0) | 2017.03.19 |