[백준 1405번] 미친 로봇 (C++)

문제링크 : https://www.acmicpc.net/problem/1405

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

int N;
double dir[4], result;
bool visited[30][30];
int dy[] = {1, -1, 0, 0};
int dx[] = {0, 0, 1, -1};

void dfs(int y, int x, int cnt, double prob)
{
    if(cnt == N)
    {
        result += prob;
        return;
    }

    for(int i=0; i<4; i++)
    {
        int ny = y + dy[i];
        int nx = x + dx[i];

        if(visited[ny][nx]) continue;
        visited[ny][nx] = 1;
        dfs(ny, nx, cnt+1, prob*dir[i]);
        visited[ny][nx] = 0;
    }
}
int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N;
    for(int i=0; i<4; i++)
    {
        cin >> dir[i];
        dir[i]/=100.0;
    }

    visited[14][14]=1;
    dfs(14, 14, 0, 1.0);

    cout.precision(10);
    cout << result;

    return 0;
}

 

먼저 예제 1을 통해 출력 값이 어떻게 나오는 지 체크하였다.

예제 1의 경우 모든 확률이 1/4이다.

 

먼저 동쪽으로 간다고 가정하면 1/4이다.

여기서 서쪽으로 가는 건 간단하지 않은 경로이므로 불가능하고, 갈 수 있는 경우의 수는 동, 남, 북 3가지 방향이다.

각 방향에 대한 확률도 1/4이므로, 동->동or남or북의 경우 1/16의 확률을 가진다.

3가지 케이스이므로 총 3/16의 확률인 것이다.

이는 동에 대해서만 따진 것이므로 나머지 서, 남, 북에 대해서도 똑같이 따지면 (3/16)*4 즉 0.75가 되는 것을 알 수 있다.

 

이를 토대로 dfs 방식을 통해 구현하였다.

먼저 입력 값은 확률에 맞게 100으로 나눠주고 시작한다.

그리고 주의할 점으로 시작 지점을 14, 14 로 잡은 것이다.

이는 시작 지점을 0, 0으로 잡을 경우 여기서 서쪽으로 이동하면 위치 상 배열의 인덱스가 음수가 나와버린다.

따라서 N의 최대 범위가 14인 것을 고려하여 음수 인덱스가 나오지 않게 중앙 값으로 시작하도록 하였다.

 

이후에는 기본적으로 카운팅을 통해 N에 도달하면 구했던 확률을 더해준다.

4방향에 때해 다음 좌표를 얻고, 단순하지 않은 경로 만을 구하기 위해 현재 위치는 방문 처리한다.

이후 다음 좌표와 카운팅, 곱해준 확률을 넘겨준다.

그리고 방문했던 좌표를 다른 경로에서 탐색가능하도록 풀어준다.

 

이를 누적하며 cnt에 도달한 모든 확률 값을 누적해서 더해주고, 소수점 자리에 주의하여 출력해준다.