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

www.acmicpc.net/problem/1405

1405번: 미친 로봇

문제

통제 할 수 없는 미친 로봇이 평면위에 있다. 그리고 이 로봇은 N번의 행동을 취할 것이다.

각 행동에서 로봇은 4개의 방향 중에 하나를 임의로 선택한다. 그리고 그 방향으로 한 칸 이동한다.

로봇이 같은 곳을 한 번보다 많이 이동하지 않을 때, 로봇의 이동 경로가 단순하다고 한다. (로봇이 시작하는 위치가 처음 방문한 곳이다.) 로봇의 이동 경로가 단순할 확률을 구하는 프로그램을 작성하시오. 예를 들어, EENE와 ENW는 단순하지만, ENWS와 WWWWSNE는 단순하지 않다. (E는 동, W는 서, N은 북, S는 남)

 

입력

첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고,  모든 확률은 100보다 작거나 같은 자연수 또는 0이다. 그리고, 동서남북으로 이동할 확률을 모두 더하면 100이다.

확률의 단위는 %이다.

 

출력

첫째 줄에 로봇의 이동 경로가 단순할 확률을 출력한다. 절대/상대 오차는 10-9 까지 허용한다.

 

예제 입력 1 

2 25 25 25 25

예제 출력 1 

0.75

 

풀이

이 문제는 DFS알고리즘을 이용하여 풀이하는 문제이다. 

N<=14라는 조건이 있으므로 방문을 확인할 배열은 30*30크기의 2차원 배열로 만들어 주었다. 그래야 N=14인 경우에도 bound를 벗어날 일이 없기 때문이다.

N과 동서남북 이동 확률을 입력받고 시작 지점을 N, N으로 잡았다.

따라서 N,N부터 동서남북으로 이동하며 방문여부를 visited[]배열에 저장하고 재귀로 들어갈때는 cnt를 1증가 시키고 재귀를 빠져나올 때는 cnt를 1 감소시키며 cnt와 n의 값이 같아지는 때를 찾는다.

또한 재귀를 빠져나올 때 그 지점의  visited[]를 다시 0으로 만들어준다.

이렇게 해야 하나의 길이 이미 방문한 지점을 다시 방문하지 않게 할 수 있다.

 

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

int n;
int visited[30][30];
double per[4]; //동서남북
int X[4] = {0, 0, 1, -1};
int Y[4] = {1, -1, 0, 0};

double per_sum;
int cnt;

void dfs(int x, int y, double now_per);

int main (void){

    int s_x, s_y;
    
    scanf("%d %lf %lf %lf %lf", &n, &per[0], &per[1], &per[2], &per[3]);
    
    s_x = n;
    s_y = n;
    
    dfs(s_x, s_y, 1.0);
    
    printf("%.10lf\n", per_sum);
}

void dfs(int x, int y, double now_per){
    int next_x, next_y;
    double next_per;
    visited[x][y] = 1;
    if(cnt == n){
        per_sum += now_per;
        visited[x][y] = 0;
        return;
    }
    cnt++;
    for(int i=0; i<4; i++){
        next_x = x+X[i];
        next_y = y+Y[i];
        if(visited[next_x][next_y]==1)
            continue;
        next_per = now_per * (per[i] / 100);
        //printf("<%d %d> <%d %d> %lf\n", x, y, next_x, next_y, next_per);
        dfs(next_x, next_y, next_per);
    }
    
    visited[x][y] = 0;
    cnt--;
}