[백준] G5 1405 미친 로봇 (java)

www.acmicpc.net/problem/1405

1405번: 미친 로봇

 

풀이

 

1) 단순한 경로 => 방문한 곳 재방문 x => isVisited[][] 배열만 잘 쓰면 장땡

2) N은 14보다 작거나 같은 자연수 이므로 map[][]의 크기는 그 2배인 28보다 크면 된다. 나는 30으로 했다

3) bfs의 스타트 지점은 상, 하, 좌, 우 로 14칸 가도 밖으로 안나갈 곳에서 시작한다. 나는 15, 15로 했다

4) 각 방향의 확률을 배열에 저장해 둔다.

5) 4방 탐색 bfs를 돌린다

5-1) 돌리면서 각 방향으로 갈 때마다 각 방향의 확률을 곱해준다.

5-2) depth가 N이 되면 확률을 결과값에 더해준다.

6) 결과값 출력

 

주의사항

 

1) x

 

package com.baekJoon;

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

public class BJ_G5_1405_미친로봇 {
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tokens;
	static int N, dir[];
	static boolean isVisited[][];
	static double answer;
	public static void main(String[] args) throws NumberFormatException, IOException {
		input = new BufferedReader(new StringReader(src));
		tokens = new StringTokenizer(input.readLine());
		N = Integer.parseInt(tokens.nextToken());
		isVisited = new boolean[30][30];
		dir = new int [4];
		for(int d=0; d<4; d++) {
			dir[d] = Integer.parseInt(tokens.nextToken());
		}
		isVisited[15][15] = true;
		dfs(15,15,0,1);
		System.out.println(answer);
//		System.out.printf("%.9f",answer);
	}

	private static void dfs(int r, int c, int cnt, double probability) {
		if (cnt == N) {
			answer += probability;
			return;
		}
		for(int d=0; d<4; d++) {
			int nr = r + dr[d];
			int nc = c + dc[d];
			
			if(isIn(nr, nc) && !isVisited[nr][nc]) {
				isVisited[nr][nc] = true;
				dfs(nr,nc,cnt+1,probability*dir[d]/100);
				isVisited[nr][nc] = false;
			}
		}
	}
	
	static boolean isIn(int r, int c) {
		return (r>=0 && c>=0 && r<30 && c<30);
	}
	
	static int dr[] = {0,0,1,-1}; // 동서남북
	static int dc[] = {1,-1,0,0};

	static String src =
			"2 25 25 25 25";
}

 

 

후기

 

 4방 탐색인데 확률이 있길래 뭔가 싶었다. 

처음에는 진짜 100번중에 25번씩 돌리는건가.. 했지만 말도안된다고 결론내리고 솔루션을 보았다.

역시나 간단한 방법이 있었고 보자마자 머리를 탁 쳤다.

요즘 솔루션을 보는 횟수가 잦아졌다. 벽에 부딛힌 느낌.

그래도 계속 나아갈것이다. 언젠가는 벽을 뚫겠지.