[BaekJoon] 1405 미친 로봇 (Java)

1.  문제 링크

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

2.  문제

요약

• 로봇은 N번의 행동을 취하는데 각 행동에서 로봇은 4개의 방향 중 하나를 임의로 선택하고 그 방향으로 한 칸 이동합니다.
• 로봇이 같은 곳을 한 번보다 많이 이동하지 않을 때, 로봇의 이동 경로가 단순하다고 합니다.
• 로봇의 이동 경로가 단순할 확률을 구하는 문제입니다.
• 입력: 첫 번째 줄에 14보다 작거나 같은 자연수인 N과 0보다 크거나 같고 100보다 작거나 같은 정수인 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어집니다. 동서남북으로 이동할 확률을 모두 더하면 100이 됩니다.
• 출력: 첫 번째 줄에 로봇의 이동 경로가 단순할 확률을 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
	static double result = 0;
	static int n;
	static double[] direction;
	
	public void getPercentage(int x, int y, boolean[][] visited, int count, double percentage) {
		if(count == n) {
			result += percentage;
			return;
		}
		int[] dx = {0, 0, 1, -1};
		int[] dy = {1, -1, 0, 0};
		for(int i = 0; i < 4; i++) {
			int cx = x + dx[i];
			int cy = y + dy[i];
			if(cx > 0 && cx < visited.length && cy > 0 && cy < visited.length) {
				if(!visited[cx][cy]) {
					visited[cx][cy] = true;
					getPercentage(cx, cy, visited, count + 1, percentage * direction[i]);
					visited[cx][cy] = false;
				}
			}
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String[] input = br.readLine().split(" ");
		br.close();
		n = Integer.parseInt(input[0]);
		direction = new double[4];
		for(int i = 0; i < 4; i++) {
			direction[i] = Double.parseDouble(input[i + 1]) * 0.01;
		}
		boolean[][] visited = new boolean[30][30];
		visited[15][15] = true;
		Main m = new Main();
		m.getPercentage(15, 15, visited, 0, 1);
		bw.write(result + "\n");
		bw.flush();
		bw.close();
	}
}

4.  접근

• 해당 문제는 DFS 및 백트래킹을 이용하여 해결할 수 있습니다.
• 최대 14번 행동을 취할 수 있기 때문에 동서남북 중 한 방향으로만 14번 가는 경우를 생각해보면 가로, 세로의 길이가 29 정도가 됩니다.
• 그렇기 때문에 중앙인 (15, 15)에 로봇을 위치시키고 가로세로 길이가 30인 2차원 배열을 생성합니다.
• DFS를 통해 로봇을 상하좌우 움직여보고 만약 2차원 배열을 벗어나거나 이미 방문한 곳을 다시 방문했다면 해당 경로는 단순한 경로가 아니므로 백트래킹을 통해 다른 방향으로 이동시킵니다.
• 이렇게 이동을 N번 하게 된다면, 그 때까지의 확률값을 더해나가며 로봇의 이동 경로가 단순할 확률을 구합니다.

public void getPercentage(int x, int y, boolean[][] visited, int count, double percentage) {
	if(count == n) {
		result += percentage;
		return;
	}
	int[] dx = {0, 0, 1, -1};
	int[] dy = {1, -1, 0, 0};
	for(int i = 0; i < 4; i++) {
		int cx = x + dx[i];
		int cy = y + dy[i];
		if(cx > 0 && cx < visited.length && cy > 0 && cy < visited.length) {
			if(!visited[cx][cy]) {
				visited[cx][cy] = true;
				getPercentage(cx, cy, visited, count + 1, percentage * direction[i]);
				visited[cx][cy] = false;
			}
		}
	}
}

1. 주어진 N을 변수 n에 넣고 주어진 동서남북 각각으로 이동할 확률을 1차원 배열 direction에 퍼센트 형태가 아닌 소수 형태로 넣습니다. 또한 로봇의 이동 경로가 단순할 확률을 나타내는 변수 result를 생성하고 값을 0으로 초기화합니다.
2. 로봇이 이동하며 각 위치를 방문했는지를 나타낼 2차원 배열 visited를 생성하고 처음 로봇을 (15, 15) 위치에 놓을 것이므로 visited[15][15] 값을 true로 변경합니다.
3. DFS 및 백트래킹을 이용하여 로봇의 이동 경로가 단순할 확률을 구합니다.
   1. 만약 지금까지 이동한 횟수가 n과 같다면 result에 지금까지 구한 확률을 더해주고 해당 재귀함수 호출을 종료합니다.
   2. 그렇지 않다면 현재 위치한 곳에서 상하좌우로 이동해보며 단순한 로봇의 이동 경로를 찾습니다.
      1. 이동한 위치가 visited 배열 내에 존재하고 이동한 위치를 아직 방문하지 않았다면
         1. 해당 위치의 visited 값을 true로 변경합니다.
         2. 현재 위치와 visited 배열 정보, (이동한 횟수 + 1), (이동하기 전까지 구한 확률 * 현재 이동한 방향에 해당하는 확률)을 매개변수로 하여 재귀함수 호출을 통해 단순한 이동 경로를 구합니다.
         3. 백트래킹을 통해 다른 방향으로도 이동해야하므로 해당 위치의 visited값을 다시 false로 변경합니다.
4. 3번 과정이 끝난 후의 result 값이 로봇의 이동 경로가 단순할 확률이므로 이를 출력합니다.