백준 1405 - 미친 로봇

문제 링크입니다. https://www.acmicpc.net/problem/1405

1405번: 미친 로봇

DFS를 사용한 문제입니다! 이동시 확률 계산이 조금 까다로운 문제였습니다.

 

문제 조건

예를 들어서 2번을 이동하고, 동서남북 이동 확률이 각각 25%라고 하겠습니다.

동->서 / 서->동 / 남->북 / 북->남 의 경우를 제외하면 전부 단순한 이동입니다. 

따라서 동 -> 동,남,북 으로 이동하면 되는데 동서남북의 경우가 있으니 전부 계산하면 1/4*1/4*3*4인 75%가 됩니다.

 

접근 방법

1. 최대 14번 이동하니 (14,14)에서 출발하도록 하고 30*30 크기의 배열 안에서 위치를 찾습니다.

2. 소수점으로 구하기 위해서 각각 확률을 입력받고 100으로 나눕니다.

3. DFS를 실행합니다.

   3-1. 이동 횟수가 N보다 작은 경우,  4방향 탐색을 합니다. 탐색한 곳이 아니였을 경우, 해당 좌표로 이동합니다.

   3-2. 이동 횟수가 N과 같은 경우, 1.0을 리턴해 이동 경로의 확률을 모두 곱해줍니다.

4. 확률을 출력합니다. 소수점 10자리까지 출력해야함으로 printf("%.10lf", ans) 를 했습니다.

 

 

자세한 것은 코드를 참고해주세요!

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>
#include <stack>
using namespace std;

int num;
double way[4];
int arr[4] = { 0,0,1,-1 };
int arr2[4] = { 1,-1,0,0 };
bool check[30][30];

double dfs(int x, int y, int cnt) {
    if (cnt == num) return 1.0;
    check[x][y] = true;
    double result = 0.0;
    for (int i = 0; i < 4; i++) {
        int xx = x + arr[i];
        int yy = y + arr2[i];
        if (!check[xx][yy]) {
            result += way[i] * dfs(xx, yy, cnt + 1);  
            check[xx][yy] = false;

        }
    }            

    return result;
}

int main() {
    cin.tie(0);
    cout.tie(0);
    cin >> num;
    for (int i = 0; i < 4; i++) {
        cin >> way[i];
        way[i] /= 100;
    }
    double ans = dfs(14, 14, 0);
    printf("%.10lf", ans);
    return 0;
}

 

 

질문 및 조언은 댓글 남겨주세요!