[백준] 미친 로봇 - 1405[ JAVA ]

| Link

www.acmicpc.net/problem/1405

1405번: 미친 로봇

---

| 문제

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

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

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

입력

첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고,  모든 확률은 100보다 작거나 같은 자연수 또는 0이다. 그리고, 동서남북으로 이동할 확률을 모두 더하면 100이다.

확률의 단위는 %이다.

출력

첫째 줄에 로봇의 이동 경로가 단순할 확률을 출력한다. 절대/상대 오차는 10-9 까지 허용한다.

---

| 풀이

• step 1 : DFS

1. 각 로봇이 움직일 수 있는 경우를 모두 탐색하기
 * 단순할 확률 구하는 방법은 : 해당 방향으로 이동할 때, 그 해당 방향으로 이동할 확률 곱하면 된다.
 
 ex. 동쪽 * ( 0. 25 ) [ 문제에서 주어진 확률 ] 

 * 방문한 곳 거치지 않고, 끝까지 도달 했을 때의 확률을 모두 더해주면 단순할 확률 구해진다.

2. 최대 N 이 14번이니까 원점 ( 15,15 ) 을 기준으로 갈 수 있는 최대 범위는 가로 30 , 세로 30의 맵
  따라서, O ( 30 * 30 ) = 900

•  * 방문한 곳 거치지 않고, 끝까지 도달 했을 때의 확률을 모두 더해주면 단순할 확률 구해진다.

---

| 어려웠던 점

• 확률 계산을 어떻게 처리해야할지 어려웠다. 해당 방향으로 이동하고 i-1 번째의 결과값에 해당방향확률 곱해서   재귀를 진행하는 방식으로 해결

---

| 코드

package 알고리즘스터디;

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

public class 미친로봇_1405 {

	static int[] dr = {0,0,1,-1}; // 동 서 남 북
	static int[] dc = {1,-1,0,0}; 
	static double answer ;
	static int N;
	static double prob[]; // 확률
	static boolean[][] visited;
	
	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];
		prob = new double[4];
		answer = 0;
		/** index
		 *   0 : 동
		 *   1 : 서
		 *   2 : 남
		 *   3 : 북
		 */
		for( int i=0; i<4; i++) {
			prob[i] = Double.parseDouble(st.nextToken()) * 0.01; 
		}
		
		visited[15][15] = true;
		dfs(0, 15,15, 1);
		System.out.println(answer);
		
	}
	
	private static void dfs(int idx, int r, int c, double probability) {
		if( idx == N ) {
			answer += probability;
			return;
		}
		
		for( int d=0; d<4; d++) {
			
			int nr = r+dr[d];
			int nc = c+dc[d];
			
			if ( isNo(nr,nc)) continue;
			
			visited[nr][nc] = true;
			dfs( idx+1, nr, nc, probability * prob[d]); // 각 방향으로 이동할 확률
			visited[nr][nc] = false;
		}
		
	}
	private static boolean isNo(int r, int c) {
		
		if ( r < 0 || r >= 30 || c<0 || c>=30 || visited[r][c]) return true;
		return false;
		
	}
}

---

| 보완할 점

 

---