백준 1405 (미친 로봇) - java

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

1405번: 미친 로봇

문제 : 

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

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

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

 

유형 : 백트랙킹 + 확률론

 

접근

• 이동 횟수를 기준으로 재귀 탈출문을 구성하는 간단한 백트랙킹 유형의 문제이다.
• 정해진 방향에 따라 해당 좌표를 방문한 적 있는가를 판단하면 된다.
  • 최대 이동은 14회이다. 한 방향으로만 14회 이동한다 가정했을 때 배열의 크기를 (31,31)로 잡고 (15,15) 부터 탐색하면 별도의 좌표계를 벗어나는 것에 대한 처리를 하지 않아도 된다.
• 문제는 확률론이다.
  • 한번의 n개의 이동 (북 -> 남 -> 동) 의 경우 북의 확률 * 남의 확률 * 동의 확률로 계산한다. (확률의 곱)
  • m개의 n개 이동의 확률 -> n개이동 확률의 합 (확률의 합)

전체 코드

import java.util.*;
import java.io.*;

public class Main {
    static int n = 0;
    static double[] per;

    static int[] dx = {0,0,0,1,-1};
    static int[] dy = {0,1,-1,0,0};

    static boolean[][]  v= new boolean[32][32];
    static double result = 0.0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        n = Integer.parseInt(st.nextToken());
        per = new double[5];

        for(int i=1;i<=4;i++){
            per[i] = Double.parseDouble(st.nextToken()) / 100.0;
        }

        v[15][15] = true;
        travel(0,15,15,1.0);
        System.out.printf("%.9f",result);
        br.close();
    }
    static void travel(int count,int x,int y,double cur){

        if(count == n){
            result += cur;
            return;
        }

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

            if(!v[nx][ny]){
                v[nx][ny] = true;
                travel(count+1,nx,ny,cur*per[i]);
                v[nx][ny] = false;
            }
        }
    }
}