[백준] 1405 미친 로봇 - 완전탐색(BruteForce) + DFS(깊이우선탐색) + 확률론(Probability) JAVA

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

1405번: 미친 로봇

코드설명

DFS(깊이우선탐색) + 확률론(Probability)  문제입니다.

 

문제 이해가 중요했던 문제입니다.

가장 헷갈릴 수 있는 부분은, 어떻게 로봇의 이동경로가 단순할 확률을 구할 수 있을까입니다.

DFS를 진행하면서 4가지 방향을 확인하며 단순경로일경우에만 이동하도록 하며 N번 이동이 완료되었을때 최종적으로 확률을 더해주면 됩니다.

 

문제에서 N개만큼 한개의 방향으로 끝까지 이동할 수 있어야합니다. N*2를 통해서 시작점이 (N, N)이므로 왼쪽으로만 이동할떄 N번 이동할 수 있고, 오른쪽으로만 이동할떄 N번 이동하기 위해서는 N*2에 +1 을 통해서 오른쪽도 N번 이동하도록 처리합니다. 그러므로 전체 Size는 N*2 + 1 이 되어야합니다. 홀수값으로 만들어주는 것 입니다.

시작점은 가장 정가운데인 (N, N)입니다. 

 

 

순서대로 주어진 동 서 남 북의 확률에 0.01 을 곱해줍니다.

for(int i=0;i<4;i++) {
    probability[i] = Double.parseDouble(st.nextToken()) * 0.01;
}

 

주어진 확률로, DFS로 아직 방문되지 않은 곳, 즉 단순경로로 가도록하여 해당 방향으로 갈 확률을 곱해나가면서 이동해나갑니다.

 

처음에는 완전탐색을 해야한다고 생각하고서 작업했지만, 코딩을 하면서 다시 원상복구하여 다음 함수가 영향을 받지 않고 완전탐색 하는 부분을 놓쳤습니다. 해당 사항을 유의합니다.

if(visited[nx][ny] == false) {
    visited[nx][ny] = true;
    simulate(level + 1, nx, ny, prob * arr[dir]);
    visited[nx][ny] = false;
}

또한 함수밖에서 해당 시작점을 방문할떄 방문처리하며 시작해야합니다.

visited[N][N] = true;
simulate(0, new Node(N, N), 1);
System.out.println(answer);

 

 

주어진 입력값을 입력하면 아래와 같이 1.220703125E-4 가 나옵니다.

입력값
14 50 50 0 0

출력값
1.220703125E-4

0.0001220703125

이는 지수표기법으로 표현해서 그렇습니다.

지수 표기법은 매우 크거나 작은 수를 간단하게 나타내는 방법입니다. 일반적으로 "E" 또는 "e" 다음에 오는 숫자는 10의 지수를 나타냅니다. 예를 들어, 1.220703125E-4는 1.220703125 × 10의 -4승을 의미합니다. 따라서 이 경우에는 0.0001220703125가 됩니다. 큰 수의 경우에도 비슷한 원리가 적용됩니다.

 

또한 확률의 입력을 double로 해야 합니다. double은 8byte(64bit)의 크기를 가집니다.

유효숫자를 표현하는 비트가 52비트이므로, 대략 15자리의 정밀도를 가집니다.반면에, float는 4바이트(32bit)의 크기를 가지며, 유효숫자를 표현하는 비트가 23비트입니다. 이는 대략 7자리의 정밀도를 가집니다.문제에서 10^-9 까지의 정밀도를 요구하므로 double을 사용해야만 값의 정밀도가 유지됩니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
	
	public static int N, M;
	public static int[][] map;
	public static int[] dx = {0,0,1,-1};
	public static int[] dy = {1,-1,0,0};
	public static boolean[][] visited;
	public static int R, D, L, U;
	public static double[] probability = new double[4];
	public static double answer = 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());
    	
    	for(int i=0;i<4;i++) {
    		probability[i] = Double.parseDouble(st.nextToken()) * 0.01;
    	}
    	
    	map = new int[31][31];
    	visited = new boolean[31][31];
    	//N이 15이니 (15, 15)에서 시작하도록 처리합니다.
    	visited[15][15] = true;
    	DFS(0, 15, 15, 1);
    	
    	System.out.println(answer);
	}
	public static void DFS(int level, int r, int c, double result) {
		if(level == N) {
			answer += result;
			return ;
			
		}
		
		for(int dir = 0; dir< 4; dir++) {
			int nr = r + dx[dir];
			int nc = c + dy[dir];
			if(nr <= 0 || nr >= 30 || nc <= 0 || nc >= 30) continue;
			
			if(visited[nr][nc] == false) {
				visited[nr][nc] = true;
				DFS(level + 1, nr, nc, result * probability[dir]);
				visited[nr][nc] = false;
			}
		}
		
	}
	
}

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;

public class Main {

	public static int N,M, K;
	public static double[] arr;
	public static double answer =0;
	public static boolean[][] visited;
	public static int[] dx = {0,0,1,-1};
	public static int[] dy = {1,-1,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());
    	arr = new double[4];
    	visited = new boolean[N*2 + 1][N*2 + 1];
    	for(int i=0;i<4;i++) {
    		arr[i] = Double.parseDouble(st.nextToken()) * 0.01;
    	}
    	
    	visited[N][N] = true;
    	simulate(0, N, N, 1);
    	System.out.println(answer);
    }
    
    public static void simulate(int level, int x, int y, double prob) {
    	if(level == N) {
//    		System.out.println(prob);
    		answer += prob;
    		return ;
    	}
    	// 'E' 동쪽으로 이동하는경우
    	for(int dir = 0; dir<4;dir++) {
    		int nx = x + dx[dir];
    		int ny = y + dy[dir];
//    		System.out.println(nx+" "+ny);
    		if(nx < 0 || nx >= 2*N+1 || ny < 0 || ny >= 2*N+1) continue;
    		if(visited[nx][ny] == false) {
    			visited[nx][ny] = true;
    			simulate(level + 1, nx, ny, prob * arr[dir]);
    			visited[nx][ny] = false;
    		}
    		
    	}
    	
    }
    
    
}