[BOJ] 백준 1405 미친 로봇

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

 Input 
2 25 25 25 25

 Output 

0.75

 

로봇은 총 2번의 행동을 수행하며, 동서남북으로 움직이는 확률은 25%로 1/4 확률에 해당

Q. 2번의 움직임에서는 같은 곳을 재방문 하는 경우는 무엇일까?

A. 동서 / 서동 / 남북 / 북남이 해당됩니다.

 

Q. 반대로 재방문 하지 않는 경우는 무엇일까?

1. 동쪽으로 이동 후 (서쪽을 제외한) 동, 북, 남 

→ (1/4 * 1/4) + (1/4 * 1/4) + (1/4 * 1/4) = 3 / 16

2. 서쪽으로 이동 후 (동쪽을 제외한) 서, 북, 남 

→ (1/4 * 1/4) + (1/4 * 1/4) + (1/4 * 1/4) = 3 / 16

3. 남쪽으로 이동 후 (북쪽을 제외한) 동, 서, 남 

→ (1/4 * 1/4) + (1/4 * 1/4) + (1/4 * 1/4) = 3 / 16

4. 북쪽으로 이동 후 (남쪽을 제외한) 동, 북, 서 

→ (1/4 * 1/4) + (1/4 * 1/4) + (1/4 * 1/4) = 3 / 16

결과적으로 (3 / 16) * 4 = 3 / 4 = 75%

 

[풀이] - DFS 이용

① 소수점을 계산해야 하므로 확률을 소숫점으로 환산하여 처리

    ex) 25% → 0.25

② DFS 탐색으로 재방문하지 않는 모든 경우의 수를 구합니다.

③ 처음 로봇의 위치를 (14, 14)로 두고 행동의 최대 개수가 14이므로 

     visited[][] 크기를 29 × 29로 설정

④ 주어진 상대오차를 고려하여 출력할 때는 아래와 같이 작성

    cout.precision(9);

    cout << fixed << DFS(14, 14, 0) << '\n';

---

#include <iostream>
using namespace std;
int N;
double probability[4];
bool visited[29][29];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

double DFS(int x, int y, int cnt){
    if (cnt == N) return 1.0;
    // 방문 표시
    visited[x][y] = true;
    double result = 0.0;
    int nextX, nextY;
    for (int i = 0; i < 4; i++){
        nextX = x + dx[i];
        nextY = y + dy[i];
        // 이미 방문한 곳은 continue
        // 주어진 명령횟수내에서는 visited[][] 크기를 벗어나지는 않는다.
        if (visited[nextX][nextY]) continue;
        // 재방문 하지 않으면서 갈 수 있는 모든 경우
        result = result + probability[i] * DFS(nextX, nextY, cnt + 1);
    }
    // 다음 탐색을 위한 원복
    visited[x][y] = false;
    return result;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N;
    for (int i = 0; i < 4; i++){
        // 소숫점으로 환산
        cin >> probability[i];
        probability[i] *= 0.01;
    }        


    // 로봇의 위치를 평면 가운데에서 시작
    // 음수를 고려하여 (14, 14)
    cout.precision(9);
    cout << fixed << DFS(14, 14, 0) << '\n';
}