[백준_1405번] 미친 로봇

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

1405번: 미친 로봇

[문제]

 통제 할 수 없는 미친 로봇이 평면위에 있다. 그리고 이 로봇은 N번의 행동을 취할 것이다. 각 행동에서 로봇은 4개의 방향 중에 하나를 임의로 선택한다. 그리고 그 방향으로 한 칸 이동한다. 로봇이 같은 곳을 한 번보다 많이 이동하지 않을 때, 로봇의 이동 경로가 단순하다고 한다. (로봇이 시작하는 위치가 처음 방문한 곳이다.) 로봇의 이동 경로가 단순할 확률을 구하는 프로그램을 작성하시오. 예를 들어, EENE와 ENW는 단순하지만, ENWS와 WWWWSNE는 단순하지 않다. (E는 동, W는 서, N은 북, S는 남)

 

[입력 조건]

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

 

[코드]

import java.util.*;

public class BaekJoon_1405 {
	static int n;
	static double answer=0;
	static boolean[][] visited=new boolean[30][30];
	static double[] percent=new double[4];
	static int[] dx= {0,0,1,-1}; // 동,서,남,북
	static int[] dy= {1,-1,0,0};
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		
		// 소수점의 형태로 바꿔 저장
		for(int i=0;i<4;i++)
			percent[i]=sc.nextDouble()*0.01;
		
		/*
		 * n은 14보다 작은 작거나 같은 자연수이기 때문에 
		 * 30*30 배열을 사용하고, 그 중 중앙에서부터 탐색을 시작한다.(배열 범위 초과 문제때문) 
		 */
		visited[15][15]=true;
		dfs(15,15,0,1);
		
		System.out.println(answer);
	}
	static void dfs(int x, int y, int depth, double result) {
		// 이동횟수 n만큼 이동했다면 해당 경로가 나올 확률 result를 answer에 누적하고 재귀호출을 종료한다.  
		if(depth==n) {
			answer+=result;
			return;
		}
		
		for(int i=0;i<4;i++) {
			int nx=x+dx[i];
			int ny=y+dy[i];
			
			/*
			 * n은 14보다 작거나 같은 자연수이기 때문에 (15,15)에서 시작하면 
			 * 아래와 같은 경우가 배열 범위를 초과한 경우와 이미 방문한 곳은 무시
			 */
			if(nx<=0||ny<=0||nx>=30||ny>=30||visited[nx][ny])
				continue;
			
			// 방문하지 않은 지점에서 백트래킹
			if(!visited[nx][ny]) {
				visited[nx][ny]=true;
				dfs(nx,ny,depth+1,result*percent[i]);
				visited[nx][ny]=false;
			}
		}
	}
}

 

[고찰]

 이번 문제는 우선 예제로 주어진 답이 어떻게 도출됐는지 이해하는 것이 우선이었다. n=2이고, 동,서,남,북의 확률은 모두 0.25로 동일할때 로봇이 갈 수 있는 방향의 경우와 각각의 확률은 아래 표와 같을 것이다.  

 

경우의 수	이동 경로		확률
1	동쪽	동쪽	1/4 * 1/4 = 1/16
2	동쪽	서쪽	1/4 * 1/4 = 1/16
3	동쪽	남쪽	1/4 * 1/4 = 1/16
4	동쪽	북쪽	1/4 * 1/4 = 1/16
5	서쪽	동쪽	1/4 * 1/4 = 1/16
6	서쪽	서쪽	1/4 * 1/4 = 1/16
7	서쪽	남쪽	1/4 * 1/4 = 1/16
8	서쪽	북쪽	1/4 * 1/4 = 1/16
9	남쪽	동쪽	1/4 * 1/4 = 1/16
10	남쪽	서쪽	1/4 * 1/4 = 1/16
11	남쪽	남쪽	1/4 * 1/4 = 1/16
12	남쪽	북쪽	1/4 * 1/4 = 1/16
13	북쪽	동쪽	1/4 * 1/4 = 1/16
14	북쪽	서쪽	1/4 * 1/4 = 1/16
15	북쪽	남쪽	1/4 * 1/4 = 1/16
16	북쪽	북쪽	1/4 * 1/4 = 1/16

 

 발생할 수 있는 16가지의 경우의 수 중 다시 제자리로 돌아오는 4가지의 경우를 뺀 12가지의 경우의 수를 모두 더하면 1/16 * 12 = 3/4 = 0.75가 된다. 즉, 모든 이동 경로중 이미 방문했던 곳을 다시 방문하는 경로를 뺀 나머지의 확률을 모두 더한 값이 정답이 되는 것이다. 

 

 한 가지 더 주의해야 할 점은 (0,0)에서 시작할 경우 서쪽과 북쪽을 탐색할 때 배열 범위를 초과하는 오류가 발생한다. 이를 방지하기 위해 30*30 크기의 배열의 중앙인 (15,15)에서 탐색을 시작하는 것이 효율적이다. (n은 최대 14이기 때문, 문제 조건)