점점 강해지고 있습니다.
[Java] 백준 1405번: 미친 로봇
풀이 방법
로봇이 단순하게 이동하는 확률을 구하는 문제이다. 단순하게 이동하는 것은 기존 밟았던 땅을 또 밟지 않는 것이다.
이를 생각하며 예제1을 풀어보자. 처음은 동서남북 모두 1/4확률이니, 처음은 동쪽으로 간다고 생각했을 때 확률은 1/4이다. 단순하게 이동할 수 있는 확률은…
- 동쪽으로 이동할 수 있다. 이 때 확률은 1/4 * 1/4 = 1/16이다.
- 서쪽으로 이동할 수는 없다. 서쪽 땅을 거쳐 이동했기 때문이다.
- 남쪽으로 이동할 수 있다. 이 때 확률은 1/4 * 1/4 = 1/16이다.
- 북쪽으로 이동할 수 있다. 이 때 확률은 1/4 * 1/4 = 1/16이다.
모두 합해서 3/16이 된다. 시작점에서 동서남북으로 이동할 수 있으니 3/16*4 = 3/4 = 0.75가 된다.
이를 DFS(백트래킹)를 통해 해결할 수 있다. N<=14이기 때문에 기존 땅을 밟지 않도록 14*2 이상인 30개의 VISITED 이중배열을 선언하여서 해결하였다.
마지막으로 절대/상대 오차는 10^-9 까지 허용하기 때문에 .10f로 출력하였다.
풀이 코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class BOJ_1405_미친_로봇 {
static double RESULT;
static int[] DR = {0, 0, 1, -1};
static int[] DC = {1, -1, 0, 0};
static double[] DIR_PERCENT;
static boolean[][] VISITED;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
DIR_PERCENT = new double[4];
VISITED = new boolean[30][30];
for(int i=0; i<4; ++i) {
DIR_PERCENT[i] = Double.parseDouble(st.nextToken()) / 100;
}
dfs(15, 15, 0, N, 1);
System.out.printf("%.10f", RESULT);
}
private static void dfs(int r, int c, int cnt, int N, double total) {
if(cnt == N) {
RESULT += total;
return;
}
VISITED[r][c] = true;
for(int d=0; d<4; ++d) {
int nr = r + DR[d];
int nc = c + DC[d];
if(nr>=0 && nr<30 && nc>=0 && nc<30 && !VISITED[nr][nc]) {
VISITED[nr][nc] = true;
dfs(nr, nc, cnt+1, N, total * DIR_PERCENT[d]);
VISITED[nr][nc] = false;
}
}
}
}
Thank You For Reading
SeungJun Jeon