[1405번] 미친 로봇

문제 출처 :

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부터 시작하는 것으로 하였다.

소스 코드 : 

#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 >>