[BOJ] 1405 미친 로봇

 

https://www.acmicpc.net/problem/1405

---

문제

통제 할 수 없는 미친 로봇이 평면위에 있다. 그리고 이 로봇은 N번의 행동을 취할 것이다.

각 행동에서 로봇은 4개의 방향 중에 하나를 임의로 선택한다. 그리고 그 방향으로 한 칸 이동한다.

로봇이 같은 곳을 한 번보다 많이 이동하지 않을 때, 로봇의 이동 경로가 단순하다고 한다. (로봇이 시작하는 위치가 처음 방문한 곳이다.) 로봇의 이동 경로가 단순할 확률을 구하는 프로그램을 작성하시오. 예를 들어, EENE와 ENW는 단순하지만, ENWS와 WWWWSN

E는 단순하지 않다. (E는 동, W는 서, N은 북, S는 남)

---

요구하는 입출력 데이터에 맞게 작성해주면 문제입니다

효율적인 탐색을 위해서,

로봇 이동경로에 따라 visited 체크가 필요하고, dfs를 기반으로한 backtracking이 필요합니다

---

참고 포인트

 

1. 최종 출력값의 부동소수점 오차를 줄이기 위해(없애기 위해) 값을 곱한 뒤 100^N 으로 나눠서 처리하는 것이 좋습니다

    (단 이 경우 long long int의 범위를 초과하기 때문에 추가적인 연산 방법이 필요합니다)

-> 반올림 연산이 필요한 경우 정교한 처리를 위해 미리 반올림 자릿수만큼 10^N을 곱하는 것과 유사한 테크닉입니다

 

2. 단순하게 브루트포스로 풀 수도 있다 4^14 == 2^28 ≒ 268,435,456 < int(3e8) 이므로 약 1초의 시간이 소요됩니다

    (이는 채점 서버의 환경 혹은 상태에 따라 달라질 수 있습니다)

 

1초당 연산량 추가 참고 자료

https://www.acmicpc.net/board/view/55142

https://www.acmicpc.net/board/view/59336

 

my solution >>

#include <bits/stdc++.h>
using namespace std;

int px[4] = {0, 0, 1, -1};
int py[4] = {1, -1, 0, 0};

void btr(int n, int move_cnt, int x, int y, bool board[][50], double& ans, vector<double>& prcts, double val){
    board[x][y] = true;
    if(n == move_cnt){
        ans += val;
        board[x][y] = false;
        return;
    }

    for(int p=0; p<4; ++p){
        int nx = x+px[p], ny = y+py[p];
        if(board[nx][ny]) continue;
        if(prcts[p] == 0) continue;
        btr(n, move_cnt+1, nx, ny, board, ans, prcts, val*(prcts[p]/100));
    }
    board[x][y] = false;
}

int main(void){
    int n; cin >> n;
    vector<double> prcts(4); for(auto &prct:prcts) cin >> prct;

    double ans = 0.0;
    bool board[50][50];
    fill(&board[0][0], &board[0][0]+50*50, false);

    board[25][25] = true;
    btr(n, 0, 25, 25, board, ans, prcts, 1);

    cout << fixed;
    cout.precision(10);
    cout << ans;
}