[TopCoder] 고장난 로봇

오늘 배울 것은 DFS와 BFS에 관련된 문제입니다.

알고리즘을 공부하다 보면 빠지지 않는 개념 중 하나입니다. 그렇기 때문에 무조건 알아야 할 것들입니다.

  문제

         

고장난 로봇이 평면 위에 있습니다. 그리고 n 번 움직입니다. 로봇은 각 단계에서 한 방향(동, 서, 남, 북) 중에 한 방향을 랜덤하게

선택해서 한 칸 움직입니다. 로봇이 동, 서, 남, 북을 선택할 확률은 north, south, east, west% 입니다.

로봇이 임의로 이동하며 같은 지점을 통과하지 않으면 성공했다고 합니다.(참고로 로봇의 시작 지점은 항상 1번째 통과 지점이 됩니다.)

로봇이 성공적으로 보행할 확률을 double 자료형으로 리턴해주세요.

  풀이

입력                       결과

n = 1                      1.0

ease = 25

west = 25

south = 25

north = 25

n은 이동 횟수이고 각 방향은 그 방향을 선택할 확률을 나타낸다. 다시말해 딱 한번 이동을 하며 각 방향을 선택할 확률은 25%로 모두 동일한 상태입니다. 

위의 경우 한번을 이동하기 때문에 어느 방향이던 같은 지점을 통과할 확률은 없습니다. 그렇기 때문에 결과는 1.0이 되겠습니다.

입력

n = 2

east = 25

west = 25

south = 25

north = 25

입력 값이 위와 같다면 각 로봇의 이동 방식을 정리할 수 있습니다. 

첫 번째 단계에서는 동 / 서 / 남 / 북

두 번쨰 단계에서는 동서남북 모두 갈 수 있습니다. 하지만 여기서 주의해야하는 것은 같은 지점을 통과하지 않는 것입니다.

동 -> 서로 가게 된다면 다시 출발한 위치로 돌아가게 되므로 실패하게 됩니다.

이 경우를 제외한 나머지 경우는 다 성공하는 케이스이므로 각각의 확률을 구해보면 

25%(동을 선택할 확률) x 25%(동을 선택할 확률)가 됩니다. 

실패할 확률을 제외한 동 / 남 / 북의 확률이 현재는 똑같기 때문에 전부 확률은 25% x  25%가 됩니다.

거기에 3을 곱하게 된다면 처음 동을 선택했을 때 성공할 확률이 구해집니다.

이렇게 첫 번째 단계에서 선택할 수 있는 경우의 수는 4가지 이므로 

0.25 x 0.25 x 3 x 4 이 확률이 우리가 구하고자 하는 답이 되겠습니다.

  코드 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Medium_02_CrazyBot {
 
    static boolean[][] visited = new boolean[100][100];
    static double[] prob = new double[4];
    static double result = 0;
 
    public void solve() {
 
        int n = sc.nextInt();
        int east = sc.nextInt();
        int west = sc.nextInt();
        int south = sc.nextInt();
        int north = sc.nextInt();
 
        result = getProbability(n, east, west, south, north);
        
        System.out.println(result);
    }
 
    public double getProbability(int n, int east, int west, int south, int north) {
 
        prob[0] = east / 100.0;
        prob[1] = west / 100.0;
        prob[2] = south / 100.0;
        prob[3] = north / 100.0;
 
        return DFS(50, 50, n);
    }
 
    public double DFS(int x, int y, int n) {
 
        int[] xMove = { 1, -1, 0, 0 };
        int[] yMove = { 0, 0, 1, -1 };
 
        if (visited[x][y])
            return 0;
        if (n == 1)
            return 1;
 
        visited[x][y] = true;
 
        for (int i = 0; i < 4; i++) {
 
            result += DFS(x + xMove[i], y + yMove[i], n - 1) * prob[i];
        }
        visited[x][y] = false;
 
        return result;
    }
 
    public static void main(String[] args) {
 
        sc.init();
 
        new Medium_02_CrazyBot().solve();
    }
 
    static class sc {
 
        private static BufferedReader br;
        private static StringTokenizer st;
 
        public static void init() {
            br = new BufferedReader(new InputStreamReader(System.in));
            st = new StringTokenizer("");
        }
 
        static String readLine() {
 
            try {
                return br.readLine();
            } catch (IOException e) {
                // TODO Auto-generated catch block
                e.printStackTrace();
            }
            return null;
        }
 
        static String readLineReplace() {
 
            try {
                return br.readLine().replaceAll("\\s+", "");
            } catch (IOException e) {
                // TODO Auto-generated catch block
                e.printStackTrace();
            }
            return null;
        }
 
        static String next() {
            while (!st.hasMoreTokens()) {
 
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    // TODO Auto-generated catch block
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
 
        static int nextInt() {
            return Integer.parseInt(next());
        }
 
        static double nextDouble() {
            return Double.parseDouble(next());
        }
 
        static Long nextLong() {
            return Long.parseLong(next());
        }
    }
}
 

출처: TopCoder 알고리즘 트레이닝 책