백준 1405번 미친 로봇

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

DFS(Depth First Search) 알고리즘을 이용하여 모든 경우를 탐색하면 되는 문제였습니다.

동서남북으로 갈 확률이 자연수로 주어지기 때문에 0.01을 곱해 확률로 만들어 주는 것과 출력할 때 소수점 10의 자리까지 출력해주는 것만 조심하면 어렵지 않게 풀 수 있는 문제인 것 같습니다.

알고리즘은 아래와 같습니다.

1. 한 방향으로 최대 14번 움직일 수 있기 때문에 (15, 15)에서 시작하고 판은 적어도 29*29여야 합니다.

2. 한번 움직일 때마다 4방향 다 움직이면서 브루트 포스(Brute Force) 알고리즘을 적용하여 답을 탐색합니다. (다른 방향으로 탐색하기 전에 전 방향에서 밟았던 칸을 다시 밟지 않은 칸으로 표시해줘야지 AC를 받을 수 있습니다.)

3. N번 움직였을 경우 누적 확률을 더해주면 됩니다.

#include <iostream>

#include <iomanip>

using namespace std;

 

const int MAX = (14 + 1) * 2;

 

typedef struct

{

        int y, x;

}Dir;

 

Dir moveDir[4] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };

 

int N;

double probability[4];

double result;

bool visited[MAX][MAX];

 

void DFS(int y, int x, double chance)

{

        //다 이동했으면 누적 확률들을 더해준다

        if (N == 0)

        {

                 result += chance;

                 return;

        }

 

        visited[y][x] = true; //밟은 땅으로 표시

        for (int i = 0; i < 4; i++)

        {

                 int nextY = y + moveDir[i].y;

                 int nextX = x + moveDir[i].x;

 

                 if (!visited[nextY][nextX])

                 {

                         N -= 1;

                         DFS(nextY, nextX, chance * probability[i]);

                         N += 1;

                         visited[nextY][nextX] = false; //다음에 밟을 땅을 다시 밟지 않음으로 표시

                 }

        }

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0); //실행속도

        cin >> N;

 

        for (int i = 0; i < 4; i++)

        {

                 cin >> probability[i];

 

                 probability[i] *= 0.01;

        }

 

        DFS(15, 15, 1.0);

 

        cout << fixed;

        cout << setprecision(10) << result << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~