[ 백준 1405 ] 미친 로봇 (C++)

백준의 미친로봇(1405) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 문제를 읽어보면, 문제는 쉬운데, 예제입력1에 대한 결과값이 왜 예제출력1 처럼 나오는지 처음에 이해가 잘되지 않았다.

   먼저, 예제입력1 (2, 25, 25, 25, 25) 에 대한 결과값이 0.75가 되는지 알아보자.

   로봇은 총 2번을 움직일 수 있으며, 동서남북으로 움직일 %는 모두 25% 라는 것이다. 즉, 동서남북 모두 1/4의 확률을 가지고

   움직이게 된다.

   그렇다면, 로봇이 총 2번 움직여야 되니, 동쪽 동쪽으로 2번 움직였다고 생각해보자.

   그렇다면 확률은 동쪽으로 움직일 확률 1/4 x 동쪽으로 움직일확률 1/4 = 1/16 이 된다.

   동쪽 북쪽으로, 동쪽 남쪽으로 움직이는 경우도 동일하게 1/16이 될 것이다. 단, 서쪽으로는 다시 움직일 수 없다.

   그렇다면, 로봇이 처음에 동쪽으로 움직이고, 그 이후에 어느방향으로 움직일 확률은 1/16 + 1/16 + 1/16 = 3/16 이 된다.

   하지만, 로봇이 무조건 동쪽으로 움직이지 않는다. 동 서 남 북 중 한방향으로 움직일 수 있다. 즉 3/16 x 4가 되어 3/4이라는

   결과값이 나온다. 그래서 답이 0.75가 된다.

2) 본인은 문제를 DFS로 해결하였다. DFS로 탐색하지 않은 정점들에 대해서만 탐색을 진행하면서, 해당 방향으로 갈 확률을

   곱해주는 식으로 구현을 하였다. 사실, 말로 설명하기 힘든 부분이 없지 않아서 소스코드를 참고하길 바란다.

  

   맵의 크기는 29 x 29로 잡아주었다. N이 14보다 작거나 같기 때문에 (14, 14)에서 시작한다고 하더라도, 14칸을 움직여도

   맵의 범위 내에 있을 수 있도록 29x29로 잡아주었다.

   또한, 답을 그대로 출력하면 틀렸습니다를 받는다.

   오차범위를 10^-9 까지 허용하기 때문에, 10^-10 까지 출력하도록 소수점을 고정시켜 주었다.

   C++에서 cout의 소수점을 고정시켜주는 방법은

   cout.precision(10)    // 소수점 아래 10자리 까지 설정

   cout << fixed << Answer // 소수점 아래 고정 10자리 까지 출력

   이 방법을 사용해줘야 맞았습니다를 받을 수 있다.

[ 소스코드 ]

#include<iostream>
 
#define endl "\n"
#define MAX 29
using namespace std;
 
int N;
double Percent[4];
bool Visit[MAX][MAX];
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
void Input()
{
    cin >> N;
    for (int i = 0; i < 4; i++)
    {
        int a; cin >> a;
        Percent[i] = a / 100.0;
    }        
}
 
double DFS(int x, int y, int Cnt)
{
    if (Cnt == N) return 1.0;
 
    Visit[x][y] = true;
    double Result = 0.0;
 
    for (int i = 0; i < 4; i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
 
        if (Visit[nx][ny] == true) continue;
        Result = Result + Percent[i] * DFS(nx, ny, Cnt + 1);
    }
 
    Visit[x][y] = false;
    return Result;
}
 
void Solution()
{
    double R = DFS(14, 14, 0);
    cout.precision(10);
    cout << fixed << R << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}