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

🔗 문제

1405번: 미친 로봇

1405번: 미친 로봇

 

🖍 풀이

 

이 문제 전에 '부분수열의 합'을 먼저 풀며 백트래킹에 대해 알고 푸는 걸 권장드립니다. 

 

 

조건을 정리해보자.

• 로봇은 동서남북 중 하나를 한칸씩 N번 이동한다. N은 14보다 작거나 같은 자연수다.
• 동서남북으로 이동할 확률이 있다. → 확률이 0만 아니면 이동이 가능하다.
• 재방문하지 않으면서 이동하는게 단순한 이동이다.

 

그냥 재방문하지 않고 N번 이동하는 확률만 구하면 된다.

1. 상하좌우 한 방향으로만 14번 가도 재방문 확인이 가능한 배열을 생성한다.
   • 최대 이동거리인 MAX*2으로 2차원 배열을 생성했다.
   • 출발지는 정중앙이다.
   • 처음에 배열 크기를 MAX로 잡고 시작점을 (0, 0)으로 해서 틀렸습니다를 봤다.
2. 확률을 계산하기 위한 과정이 필요하다.
   • 입력되는 퍼센테이지를 0.01 곱해줘 확률로 변경해준다.
     • 25% → 0.25
   • 이동할 때마다 이동한 방향과 현재 확률을 곱해준다. 우리가 구하는 건 확률이니까!
     • 확률이 0이면 이동이 "불가"하다는 점
     • 같은 곳에 재방문을 하면 단순한 경로가 아니라는 점
   • 출력 시 1이 아니라 1.0 으로 출력해야 하며 소수점 오차 범위가 10의 9승이다. 그냥 소수점을 살려야 한다는걸 유의하자. 그래서 소수점을 표현하기 위해 std::cout.precision을 사용해주었다.

 

💾  소스

#include <iostream>
#include <cmath>

const int MAX = 30;
const int dx[4] = {0, 0 , 1, -1};
const int dy[4] = {-1, 1, 0, 0};

int N;
double probability[4];
bool visited[MAX][MAX] = {false, };
double answer = 0.0;

void solve(int r, int c, int depth, double prob)
{
    if(depth == N)
    {
        answer += prob;
        return;
    }
    
	for(int d=0; d<4; ++d)
    {
        int x = r + dx[d];
        int y = c + dy[d];
        
        if(probability[d] == 0 || visited[x][y])
            continue;

            visited[x][y] = true;
            solve(x, y, depth+1, probability[d]*prob);
            visited[x][y] = false;
    }
}

int main()
{
    int tmp = 0;
    std::cin >> N ;
    for(int i = 0; i<4; ++i)
    {
        std::cin >> tmp;
        probability[i] = tmp*0.01;
    }
    
    visited[15][15] = true;
    solve(15, 15, 0, 1);

    std::cout.precision(20);
    std::cout << answer ;

    return 0;
}