[백준/java] 1405. 미친 로봇

문제 링크 -https://www.acmicpc.net/problem/1405

🌱 문제

🌱 풀이

• 단순하지 않을 확률을 구한 후 (이동경로가 단순할 확률) = 1 - (이동경로가 단순하지 않을 확률)로 정답을 구했다. 이때, 단순하지 않는 경우는 이미 방문한 곳을 또 방문하는 경우이다.
• N<=14이므로 29*29 배열을 선언해서 가운데 위치 (14,14)가 로봇의 처음 위치라고 가정하였다.
• dfs를 돌면서 현재 좌표인 (r,c)에 오는데에 걸리는 확률을 갱신해준다. sum은 (이동경로가 단순하지 않을 확률 ) = ( 방문했던 곳을 다시 방문할 확률) 을 저장하는 변수이다.
  - 만약 현재 좌표가 이미 방문했던 좌표라면 현재까지의 확률을 sum에 더해주고 더이상 dfs에 들어가지 않는다. 왜냐하면 더 들어가더라도 이미 그 이동경로는 단순하지 않은 경우로 확정되었기 때문이다.
  - 현재 좌표가 방문하지 않은 좌표라면 방문 체크 후 다음 좌표로 dfs를 통해 이동한다. (다음 좌표로 가는데 필요한 확률도 반영해준다)
• dfs가 끝나면 answer=1-sum으로 정답을 구하면 된다.

🌱 코드

package week06.boj_1405;

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

/*
 *(이동경로가 단순할 확률) = 1 - (이동경로가 단순하지 않을 확률)로 구했다.
 * 단순하지 않는 경우는 이미 방문한 곳을 또 방문하는 경우이다.
 *
 */
//1405. 미친 로봇 
public class Somyeong {
	static int n;
	static double p[];
	static double answer;
	static double sum; // 단순하지 않을 확률의 합
	static boolean visited[][];
	static int r, c;
	static int dr[] = { 0, 0, 1, -1 }; // 동 서 남 북
	static int dc[] = { 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());
		p = new double[4];
		visited = new boolean[29][29];
		n = Integer.parseInt(st.nextToken());
		for (int i = 0; i < 4; i++) {
			p[i] =Double.parseDouble(st.nextToken());
		}
		
		// N<=14이므로 29*29 배열을 선언해서 딱 가운데 위치(14,14)에 현재 로봇이 있다고 가정한다.
		r = 14;
		c = 14;
		visited[r][c]=true;
		dfs(0, r, c, 1);
		answer=1-sum;
		System.out.println(answer);

	}

	public static void dfs(int cnt, int r, int c, double pro) { //(이동횟수, 로봇의 r좌표, 로봇의 c좌표, 현재지점에 오는데에 필요한 확률)
		if (cnt == n) {
			return;
		}
	
		for (int i = 0; i < 4; i++) {
			int nr = r + dr[i];
			int nc = c + dc[i];

			if(visited[nr][nc]==false) { 
				visited[nr][nc]=true;
				dfs(cnt + 1, nr, nc, pro * (p[i] / 100));
				visited[nr][nc]=false;
			}
			else // 이미 방문했던곳을 또 방문할경우 현재까지의 확률을 sum에 더해주고 더이상 dfs를 들어가지 않는다.
				sum+=pro*(p[i]/100);

		}
	}

}