[DFS] 1405번 미친 로봇

1405번 미친 로봇

 

https://www.acmicpc.net/problem/1405

 

문제

통제 할 수 없는 미친 로봇이 평면위에 있다. 그리고 이 로봇은 N번의 행동을 취할 것이다.

각 행동에서 로봇은 4개의 방향 중에 하나를 임의로 선택한다. 그리고 그 방향으로 한 칸 이동한다.

로봇이 같은 곳을 한 번보다 많이 이동하지 않을 때, 로봇의 이동 경로가 단순하다고 한다. (로봇이 시작하는 위치가 처음 방문한 곳이다.) 로봇의 이동 경로가 단순할 확률을 구하는 프로그램을 작성하시오. 예를 들어, EENE와 ENW는 단순하지만, ENWS와 WWWWSNE는 단순하지 않다. (E는 동, W는 서, N은 북, S는 남)

 

입력

첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고, 모든 확률은 100보다 작거나 같은 자연수 또는 0이다. 그리고, 동서남북으로 이동할 확률을 모두 더하면 100이다.

 

출력

첫재 줄에 로봇의 이동 경로가 단순할 확률을 출력한다. 절대/상대 오차는 10⁻⁹ 까지 허용한다.

 

예제 입력

2 25 25 25 25

 

예제 출력

0.25

 

해결방법

문제를 이해하는데 한참 걸린 문제이다... (다른 블로그 를 참고하여 문제를 이해함!)

 

⭐️ 솔루션 ⭐️

• 로봇은 E W N S 의 4방향으로 이동이 가능하다
• 중복되지 않은 경로로 이동을 하면 그 경로는 단순하다
• 경로 이동 시, 방향의 확률을 곱해준다
• 만약 무사히 이동했으면 이는 단순한 경로이므로 ans 에 확률을 더해준다

 

만약 n=2 이고, 동서남북의 확률이 전부 25 라고 가정해보자

확률의 수치는 1/100 을 곱한 0.25가 될 것 이다

 

이제 로봇의 현재 위치에서 4방향으로 탐색을 시작한다

동쪽에는 E S E E E N 의 3가지 단순 경로가 존재한다

각각의 확률은 0.0625 이다. 따라서 동쪽 단순 경로의 합은 0.1875 이다

 

이렇게 4방향을 모두 탐색한다면 0.75 라는 확률을 얻을 수 있다!!

 

 

⭐️ 시간 복잡도 ⭐️

시간 복잡도는 한 노드에서 4가지 탐색이 가능하고, 최대 14번 움직일 수 있으므로 O(4^14) 이다

하지만 단순하지 않은 경로는 탐색하지 않기 때문에 시간 초과가 발생하지 않는다

 

⭐️ 문제에 대한 접근 ⭐️

이 문제는 map 의 크기에 대해 언급하지 않는다

하지만 로봇은 최대 14번 이동 가능하다

따라서 어느방향으로 14번을 이동해도 맵을 벗어나면 안된다

따라서 MAX 값은 29가 되고, 로봇의 초기 위치는 (14,14) 가 될 것이다

 

⭐️ 출력 ⭐️

이 문제의 출력조건은 printf("%.10lf\n",ans); 이다

문제에서 절대/상대 오차는 10⁻⁹ 까지 허용한다. 라는 조건을 제시했기 때문에

double형을 의미하는 %lf 와 소수점 10자리 까지 표시하라는 %.10 의 형식지정자를 사용한 것이다

 

 

소스코드

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <algorithm>
#define MAX 29
#define INF 987654321
using namespace std;

int n;
double P[4];
double ans;

bool visited[MAX][MAX];

int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};

void dfs(int x,int y,int cnt,double res){
    // 로봇이 n번 이동을 함 (= 단순한 경로)
    if(cnt == n){
        ans += res;
        return;
    }
    
    visited[x][y] = true;
    
    for(int i=0; i<4; i++){
        int nx = x + dx[i];
        int ny = y + dy[i];
        
        if(!visited[nx][ny]){
            dfs(nx,ny,cnt+1,res*P[i]);
        }
    }
    
    visited[x][y] = false;
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    // ios_base::sync_with_stdio(false);
    // cin.tie(NULL); cout.tie(NULL);
    
    scanf("%d",&n);
    
    for(int i=0 ;i<4; i++){
        int d;
        scanf("%d",&d);
        P[i] = d * 0.01;
    }
    
    ans = 0.0;
    dfs(14,14,0,1.0);
    printf("%.10lf\n",ans);
    
    return 0;
}