Easy is Perfect

[백준] 1405번 C/C++ 풀이 _ 미친 로봇

  • melonicedlatte
  • Nov 11, 2018


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

미친 로봇 성공스페셜 저지

시간 제한메모리 제한제출정답맞은 사람정답 비율
2 초128 MB257591760832.306%

문제

통제 할 수 없는 미친 로봇이 평면위에 있다. 그리고 이 로봇은 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를 이용하여 문제를 해결합니다.
dfs를 구성하는 트리에서 엣지를 지나가면 확률이 곱해진다고 생각하면 됩니다. 

dfs를 사용한 풀이는 크게 2가지로 나눠집니다. 


첫 번째 dfs는 확률 값이 리프노드에 가면 return 을 계속해줘서, 원하는 노드의 확률 값을 구할 수 있는 풀이입니다.


두 번째 dfs는 확률 값이 dfs의 파라미터를 통하여 전달되어서, 원하는 노드의 확률 값을 구할 수 있는 풀이입니다.
자세한 내용은 풀이를 확인해주세요~

확률 값이 리프 노드에서 거슬러 올라오는 dfs 풀이 소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <cstdio>
#include <algorithm>
using namespace std;
int n, visited[30][30];
double p[4];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
 
double dfs(int x, int y, int cnt) {
    if (cnt == 0)return 1.0;
    double ret = 0.0;
    visited[x][y] = true;
    for (int i = 0; i < 4; i++) {
        int cx = x + dx[i];
        int cy = y + dy[i];
        if (visited[cx][cy])continue;
        ret += dfs(cx, cy, cnt - 1)*p[i];
    }
    visited[x][y] = false;
    return ret;
}
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < 4; i++) {
        scanf("%lf", &p[i]);
        p[i] /= 100.0;
    }
    printf("%.9lf\n", dfs(15, 15, n));
    return 0;
} 
cs

확률 값이 각 단계로 전파 되어가는 dfs 풀이 소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
    static int n;
    static double ret = 0.0;
    static boolean[][] visited;
    static double[] possibility = new double[4];
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        st = new StringTokenizer(br.readLine(), " ");
        n = Integer.parseInt(st.nextToken());
        visited = new boolean[30][30];
 
        for(int i=0; i<4; i++)           
            possibility[i] = Double.parseDouble(st.nextToken()) / 100.0;
 
        tracking(0, 1.0, 14, 14);
        System.out.println(ret);
    }
 
    static void tracking(int depth, double p, int x, int y) {
        visited[y][x] = true;
 
        if(depth == n) ret = ret+p;        
        if(depth < n) {
            for(int i=0; i<4; i++) {
                int nextY = dy[i] + y;
                int nextX = dx[i] + x;
 
                if(!visited[nextY][nextX]) 
                    tracking(depth + 1, p * possibility[i], nextX, nextY);
            }
        }
        // n만큼 이동 완료하고 나면, visited 초기화
        visited[y][x] = false;
    }
}
cs



Search