문제 링크입니다: 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
지적, 조언, 질문 환영입니다! 댓글 남겨주세요~
'알고리즘 > BOJ' 카테고리의 다른 글
백준 2875번 대회 or 인턴 (7) | 2018.07.23 |
---|---|
백준 14889번 스타트와 링크 (2) | 2018.07.23 |
백준 1744번 수 묶기 (0) | 2018.07.23 |
백준 11559번 Puyo Puyo (2) | 2018.07.22 |
백준 6593번 상범 빌딩 (0) | 2018.07.22 |