# [Gold IV] 미친 로봇 #### [문제 링크](https://www.acmicpc.net/problem/1405) ## 문제 설명 <p>통제 할 수 없는 미친 로봇이 평면위에 있다. 그리고 이 로봇은 N번의 행동을 취할 것이다.</p> <p>각 행동에서 로봇은 4개의 방향 중에 하나를 임의로 선택한다. 그리고 그 방향으로 한 칸 이동한다.</p> <p>로봇이 같은 곳을 한 번보다 많이 이동하지 않을 때, 로봇의 이동 경로가 단순하다고 한다. (로봇이 시작하는 위치가 처음 방문한 곳이다.) 로봇의 이동 경로가 단순할 확률을 구하는 프로그램을 작성하시오. 예를 들어, EENE와 ENW는 단순하지만, ENWS와 WWWWSNE는 단순하지 않다. (E는 동, W는 서, N은 북, S는 남)</p> ## 입력 <p>첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고, 모든 확률은 100보다 작거나 같은 자연수 또는 0이다. 그리고, 동서남북으로 이동할 확률을 모두 더하면 100이다.</p> <p>확률의 단위는 %이다.</p> ## 출력 <p>첫째 줄에 로봇의 이동 경로가 단순할 확률을 출력한다. 절대/상대 오차는 10^-9 까지 허용한다.</p> ## 풀이 #### N이 최대 14여서 모든 가능한 경우의 수는 겹치는 것을 포함해서 총 4¹⁴ = 268,435,456개 입니다. 하지만 겹치는 것을 빼면 굉장히 적어지기에 순회하더라도 시간 안에 돈다는 사실을 알 수 있습니다. (실제로 직접 경우의 수를 세보니 총 2,374,444개 였습니다.) #### 움직이는 것은 상하좌우 14칸씩 움직일 수 있으니 29x29 크기의 visited배열을 만들면 DFS로 쉽게 구현을 할 수 있습니다. 이동할 때마다 각 방향으로의 확률을 곱해주면서 깊이가 N이 되었을 때의 확률을 전부 더해주면 됩니다. ``` c++ #include<bits/stdc++.h> using namespace std; typedef long double ld; bool visited[29][29]; // 방문했는지 확인할 배열 int moveX[4] = {1, -1, 0, 0}; // (동, 서, 남, 북) int moveY[4] = {0, 0, 1, -1}; ld n, percent[4], total; void back(int depth, int x, int y, ld cur) { if(depth==n) { // 방문 횟수가 끝나면 이번 단순 이동의 확률 추가 total += cur; return; } visited[x][y]=true; for(int i=0;i<4;i++) { // 직접 움직여보면서 단순한 이동 찾기 int nx = x+moveX[i]; int ny = y+moveY[i]; if(!visited[nx][ny]) { back(depth+1, nx, ny, cur*percent[i]); } } visited[x][y]=false; } int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n; for(int i=0;i<4;i++) { // 네 방향의 확률 입력 cin >> percent[i]; percent[i] /= 100; } back(0, 14, 14, 1); cout << setprecision(9) << fixed << total; } ```