백준 1405. 미친로봇 (DFS)

www.acmicpc.net/problem/1405

1405번: 미친 로봇

문제제목 : 미친로봇

문제난이도 : 골드5

문제유형 : DFS

문제

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

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

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

입력

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

확률의 단위는 %이다.

출력

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

접근방식

<<확률>>

동 : 0.25 서: 0.25 남:0.25 북:0.25 의 확률을 가지고 있을 때,

동->동 으로 이동할 확률은 0.25 * 0.25이다.

동->서->동으로 이동할 확률은 0.25 * 0.25 * 0.25 이다.

 

따라서 로봇이 지나갔던 위치를 지나지 않는 경로의 확률 구해서 다 합산해주면

그 값이 로봇의 단순한 이동경로 확률이 된다.

 

package week6;

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class BOJ1405 {
	public static boolean[][] map;
	public static double[] dir;
	public static int[] dx = {1, -1, 0, 0};
	public static int[] dy = {0, 0, -1, 1};
	public static double result = 0;
	public static int N;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		//입력
		String[] input = br.readLine().split(" ");
		N = Integer.parseInt(input[0]);
		dir = new double[4];
		for (int i = 0; i < 4; i++) {
			dir[i] = Integer.parseInt(input[i + 1]) * 0.01; //퍼센트 저장
		}
		
		map = new boolean[29][29];
		
		DFS(14, 14, 0, 1);
		
		System.out.println(result);
	}
	
	// 단순한 경로 개수 세기
	public static void DFS(int x, int y, int count, double total) {
		if (count == N)  {	
			result += total;
			return;
		}
		map[x][y] = true;
		
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			if (!map[nx][ny]) {
				map[nx][ny] = true;
				DFS(nx, ny, count + 1, total * dir[i]);
				map[nx][ny] = false;
			}
		}
	}
}

 

---

문제를 읽고 DFS가 적합할 지 BFS가 적합할 지 충분히 확인해야한다.

멋대로 BFS썼다가 시간 엄청 허비했다 ㅠㅠ