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

1405번: 미친 로봇

백트래킹

---

1. 문제 해결 아이디어

 

로봇이 최대 14번 움직이므로 14번 동안 자유롭게 움직일 수 있는 좌표 Map[32][32]를 설정해주었다.

 

초기 좌표를 적당한 중간 좌표로 잡아주고 백트래킹 dfs를 해준다.

 

움직일 때마다 확률을 곱해줘야 하므로 함수의 인자로 초기값 1을 가지는 확률 변수를 넘겨준다.

 

이동 중에 방문했던 곳을 다시 들리게 된다면 지금까지 곱해진 확률을 결과값에 더해준다. (단순하지 않을 때만 더해 줌)

 

결과는 단순한 경우를 찾으므로 1-결과를 하고 소수점 10자리정도 출력해주면 끝

---

2. 코드

#include <iostream>
 
using namespace std;
 
int N, Map[32][32];
double per[4];
int dr[4] = {0, 0, 1, -1}, dc[4] = {1, -1, 0, 0};
 
double result;
 
void solve(int cnt, int r, int c, double chance){
    if(cnt == N) return;
    
    Map[r][c] = 1;
    
    for(int i = 0; i < 4; i++){
        int nr = r + dr[i];
        int nc = c + dc[i];
        
        if(Map[nr][nc]){
            result += (chance * (per[i]/100));
            continue;
        }
        
        solve(cnt+1, nr, nc, chance * (per[i] / 100));
    }
    
    Map[r][c] = 0;
}
 
int main(){
    cin >> N;
    cin >> per[0] >> per[1] >> per[2] >> per[3];
    
    solve(0, 15, 15, 1);
    
    printf("%.10lf", 1-result);
    return 0;
}