백준 1405번 미친 로봇 - C++(cpp) 풀이

---

 

1. DFS로 모든 경우 4^N가지를 다 고려한다.
2. N칸 모두 이동했을 경우 해당 루트로 이동할 확률을 더한다.

 

1. DFS로 모든 경우 4^N가지를 다 고려한다.

 N이 작기 때문에 모든 경우를 다 고려하는 방법을 생각해볼 수 있다. N=14이므로 모든 경우의 수는 4^14 = 268,435,456이 된다. 중간에 방문했던 곳을 또 방문했을 경우 가지치기가 되므로 실제 탐색 횟수는 이것보다 더 적어진다.

 

2. N칸 모두 이동했을 경우 해당 루트로 이동할 확률을 더한다.

 N칸을 이동했을 때 해당 루트로 이동할 확률은 매 이동마다 해당 방향으로 이동할 확률의 곱과 같다. dfs에서 매 depth마다 이동 확률을 누적해서 전달해주면 된다.

반응형

---

#include <iostream>
#include <cmath>
#include <string.h>

using namespace std;

typedef long double ld;

int N, e, w, s, n;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
ld dp[4];
bool visit[30][30];
ld ans = 0;

void dfs(int x, int y, ld p, int cnt) {
    if (visit[x][y]) return;
    if (cnt == N) {
        ans += p;
        return;
    }
    
    visit[x][y] = true;
    for (int i=0; i<4; i++) dfs(x+dx[i], y+dy[i], p*dp[i], cnt+1);
    visit[x][y] = false;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N >> e >> w >> s >> n;
    dp[0] = (ld)s/100; dp[1] = (ld)n/100; dp[2] = (ld)w/100; dp[3] = (ld)e/100;
    
    dfs(14, 14, 1, 0);
    
    cout << fixed;
    cout.precision(20);
    cout << ans;

    return 0;
}