미친 로봇 [백준 1405][Java][DFS][확률]

 

[광고 누르면 오늘의 행운 상승!!]

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

1405번: 미친 로봇

DFS 확률 문제

1. N이 최대 14까지 나오므로 30개의 맵을 선언한다.

2. 14,14좌표에서 DFS를 시작한다.

3. DFS를 나아가면서 PERCENT끼리 곱해간다 (확률의 곱셈) 

4. CNT == N일때 이동거리를 모두 소모했으므로 PERCENT를 최종ans에 더한다.

5. 모두 더해진 ans를 출력한다.

package Study2;

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

public class 미친로봇 {
	public static int[] dx = {0,0,1,-1};
	public static int[] dy = {1,-1,0,0};
	public static double dir[];
	public static boolean visit[][];
	public static int N;
	public static double ans;
	
	public static void main(String[] args) throws Exception{
		System.setIn(new FileInputStream("test.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		N = Integer.parseInt(st.nextToken());
		dir  = new double[4];
		visit = new boolean[30][30];
		
		for (int i = 0; i < 4; i++) {
			dir[i] = Integer.parseInt(st.nextToken()) * 0.01;
		}
		
		visit[14][14] = true;
		dfs(14,14,0,1.0);
		
		System.out.println(ans);
		
	}
	private static void dfs(int row, int col, int cnt, double percent) {
		if(cnt == N) {
			ans += percent;
			return;
		}
		
		for (int i = 0; i < 4; i++) {
			if(dir[i] == 0) continue;
			
			int nx = row + dx[i];
			int ny = col + dy[i];
	
			if(!visit[nx][ny]) {
				visit[nx][ny] = true;
				dfs(nx,ny,cnt + 1 ,dir[i] * percent);
				visit[nx][ny] = false;
			}
		}
	}
}