[BOJ] 1405. 미친로봇

미친 로봇 성공스페셜 저지

클릭시 이동합니다.

어떻게 풀까?

중요한 것은 이전에 왔던 경로에 도착하지 않는 경우의 확률만 구해야 한다는 것입니다.

즉, DFS를 통해서, N번을 이동하면서, 자신의 위치를 visit처리 해준 다음에, visit처리 되지 않은 방향으로만 이동합니다!

그리고, 각 방향으로의 확률이 있기 때문에, 자신이 현재 도착한 위치의 확률 * 다음으로 이동할 확률을 계속 곱해가면서, 

자신의 현재 위치에 대한 확률을 계속 가지고 있습니다!

그리고, N번의 이동을 완료했으면, 결과 확률에 그 확률을 더해주고, 이전 상황으로 돌아가서, 다른 방향을 탐색합니다!

그림으로 예를 들어 드리겠습니다!

처음엔 이 장소에서 시작합니다!

오른쪽으로 이동할 수 있습니다!

예제에서는 오른쪽 확률이 0.25이기 때문에, 현재 확률 1에서 0.25를 곱해줍니다!

이동을 하고나면, 지나왔던 자리에는 visit 체크를 해줍니다!

일단 n이 10인 경우를 가정하겠습니다!

위 방법처럼 움직이다 보면 위의 상황이 나오는 경우도 있을 것 입니다!

위로 이동하려고 할 경우, 이미 visit처리가 되어있기 때문에 이동하지 않습니다!

오른쪽의 경우에는 이동할 수 있기 때문에 이동을 합니다!

해당 지점에 도착할 확률은, 이전에 있던 확률 p에서 오른쪽으로 이동할 확률입니다!

그리고 10번 이동을 완료했기 때문에, 해당 확률을 결과값에 더해줍니다!

또한, 10번 이동했기 때문에 이전 상태로 돌아옵니다!

이 때, visit 처리했던 부분을 다시 원래대로 돌려줍니다.

왼쪽으로도 이동이 가능합니다!

이동합니다!

이번에는 현재 확률에 왼쪽 확률을 곱하고, 10번 이동했기 때문에 결과값에 해당 확률을 더해줍니다!

이렇게, 백트랙킹과 DFS를 이용하면서 이동할 수 있는 모든 경우의 확률을 더해주면 답을 구할 수 있습니다!

코드

#pragma once
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<string>
using namespace std;
typedef pair<int, int> PII;
int n;
int dr[4] = { 0,0,1,-1 };
int dc[4] = { 1,-1,0,0 };
bool map[30][30];
double p[4];
 
double res = 0;
 
void getPath(int r, int c, int depth, double pro) 
{
    if (n == depth) {
        res += pro;
        return;
    }
    
    map[r][c] = true;
 
    for (int d = 0; d < 4; d++) {
        int next[2] = { r + dr[d], c + dc[d] };
        
        if (map[next[0]][next[1]]) continue;
        getPath(next[0], next[1], depth + 1, pro*p[d]);
    }
    
    map[r][c] = false;
}
int main() 
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> p[0] >> p[1] >> p[2] >> p[3];
 
    for (int i = 0; i < 4; i++)
    {
        p[i] /= 100.;
    }
    
    getPath(15, 15, 0, 1);
 
    cout.setf(ios::fixed);
    cout.precision(9);
 
    cout << res << '\n';
    return 0;
}

시간 복잡도

시간 복잡는 정말로 햇갈리는데... 한번 이동할때 마다 이동할 수 있는 공간이 최대 3 개씩 늘어나니까 이라고 생각합니다!

여담

처음에 아무 생각없이 visit 체크를 해주면서 BFS로 풀면 될 것 같다는 생각을 해서 꼬여버린 문제였습니다!

BFS의 경우에는 위->오른쪽 으로 가는것과 오른쪽 -> 위로 가는것이 결국 같은 공간으로 가는 것으로 보이고,

이에 대한 처리가 적절하게 이뤄지기 힘들기 때문에 좋은 방법이 아니었습니다!

오랜만에 푸는 dfs문제라서 그런지 조금 햇갈렸네요!