[백준 1405] 미친 로봇

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

1405번: 미친 로봇

• 유형
  dfs
• 로직
  dfs를 돌린다 -> 재방문 하는 곳은 리턴 -> dfs를 돌리면서 방향에 맞는 확률도 같이 계산해서 파라미터로 넘겨준다
  -> 주어진 N 만큼 깊이로 탐색을 했을 시 확률을 더해준다
• 코드

package 백준;

import java.util.Scanner;

public class 미친로봇1405 {
	static int dr[]= {0,0,1,-1};
	static int dc[]= {1,-1,0,0};
	static boolean visit[][];
	static int n;
	static double d[]=new double[4];
	static int map[][];
	static double total=0;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		for (int i = 0; i < d.length; i++) {
			d[i] = sc.nextInt()*0.01;
		}
		map = new int[30][30];
		visit = new boolean[30][30];
		visit[14][14]=true;
		dfs(14,14, 0, 1);
		System.out.println(total);
	}
	static void dfs(int r, int c, int depth, double sum) {
		//총 n 번 이동한 경우
		if(depth == n) {
			total+=sum;
			return;
		}
		for (int i = 0; i < d.length; i++) {
			int nr = r+dr[i];
			int nc = c+dc[i];
			if(visit[nr][nc])
				continue;
			visit[nr][nc] = true;
			dfs(nr,nc, depth+1, d[i]*sum);
			visit[nr][nc]=false;
		}
	}
}
/*
재방문x -> 단순함
재방문o -> 단순안함
돌아오지 않는 경우들/전체  -> n을 재한 걸고 -> 재방문 한경우 카운트 -> 끝까지 간 경우 카운트
마지막에 나누셈을 계산

*/