[백준 - 1405] 골드5 - 미친 로봇

www.acmicpc.net/problem/1405

1405번: 미친 로봇

 

1. 유형

dfs, 백트래킹

 

2. 풀이

• 구현기능: 중복 탐색, 완전탐색, 확률계산
• 자료구조: 배열

단순할 조건 - 왔던 좌표를 다시 방문하지 않는 경우

 

즉, dfs 사용해서 4방향에 대한 완전 탐색을 해야함.

 

이떄, 방문한 좌표를 만날 경우 백트래킹을 한다.

 

주의 할점은 좌표를 0,0 부터 시작하면 인덱스 에러가 나기 때문에,

 

14, 14 부터 시작하고 배열 크기는 [29][29]로 잡음.

 

 

3. 코드

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

public class Main {
	static int dr[] = { 0, 0, -1, 1 };
	static int dc[] = { 1, -1, 0, 0 };
	static int N, per[];
	static boolean visit[][];
	static double res;

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		N = Integer.valueOf(st.nextToken());
		per = new int[4];
		for (int i = 0; i < 4; i++) {
			per[i] = Integer.valueOf(st.nextToken());
		}
		res = 0;
		visit = new boolean[29][29];
		dfs(0, 14, 14, 1);
		System.out.println(res);
	}

	static void dfs(int idx, int r, int c, double sum) {
		visit[r][c] = true;
		if (idx == N) {
			res += sum;
			return;
		}
		for (int i = 0; i < 4; i++) {
			int nr = r + dr[i];
			int nc = c + dc[i];
			if (visit[nr][nc]) {
				continue;
			}
			dfs(idx + 1, nr, nc, sum * (double)(per[i]) / 100);
			visit[nr][nc] = false;
		}
	}
}