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

문제

백준 1405 미친 로봇 C++

1405번: 미친 로봇

풀이

DFS를 활용하여 전체 탐색합니다.

4^14이라 시간 초과가 발생할 것 같지만, 중간에 경로가 겹치면 그 이후 경로는 탐색하지 않는 식으로 접근하면 더 빨리 해결이 가능합니다.

소스 코드

#include <iostream>
using namespace std;
 
// 명령 개수, 북남서동 확률
int N;
double proArr[4];
double simple;
int dx[] = { -1, 1, 0, 0 };
int dy[] = { 0, 0, -1, 1 };
bool visited[100][100];
void dfs(int x, int y, double probaility, int cnt) {
    // 경로 겹치면 return
    if (visited[y][x]) {
        return;
    }
    visited[y][x] = true;
    // cnt만큼 움직였는데 겹치지 않았으면 simple에 지금까지의 확률 더해주기
    if (cnt == N) {
        simple += probaility;
        visited[y][x] = false;
        return;
    }
    // 북남서동 확인
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        dfs(nx, ny, probaility * proArr[i], cnt + 1);
    }
    visited[y][x] = false;
}
int main()
{
    cout << fixed;
    cout.precision(18);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    for (int i = 0; i < 4; i++) {
        double prob;
        cin >> prob;
        proArr[i] = prob / 100.0;
    }
    dfs(50, 50, 1, 0);
    cout << simple;
    return 0;
}