[백준 - 1405] 미친 로봇 - Java

문제 설명

 

1405번: 미친 로봇

 

접근 방법

해당 문제는 DFS를 통한 백트래킹을 이용하여 해결할 수 있었습니다.

 

우선 로봇이 이동하는 평면을 나타내야 하는데, 로봇은 이 평면의 중심상에서 출발하여 동, 서, 남, 북 각각의 방향으로 이동할 수 있어야 합니다. 이때 이러한 평면의 전체 크기는 주어지는 정수 n의 크기와 규칙이 있었습니다.

 

if n = 1, then 3 x 3 board

if n = 2, then 5 x 5 board

if n = 3, then 7 x 7 board...

board's size : (2n + 1) x (2n + 1)

 

이때 평면의 크기를 결정하는 것은 로봇이 평면의 중심에서 하나의 방향으로만 이동했을 때의 거리입니다. 예를 들어, n이 3일 때 로봇이 북쪽으로만 이동하게된다면 로봇의 중심에서 거리가 n에 해당됩니다. 반대로 남쪽으로만 이동하게 되는 경우도 있을 수 있으므로 한변의 길이는 2n + 1이 되어야 합니다.

 

이후에, 동, 서, 남, 북 각각의 방향별 확률을 HashMap을 이용하여 저장했는데, 이는 추후 DFS 탐색 시 이를 활용해 확률이 존재하는(0% 초과) 방향에 대해서만 탐색하도록 하기 위함이었습니다.

 

        Map<String, Double> percentagesByDirection = new HashMap<>();
        
        // 동, 서, 남, 북
        String[] directions = {"EAST", "WEST", "SOUTH", "NORTH"};
        int percentage;
        for (String direction : directions) {
            percentage = Integer.parseInt(st.nextToken());
            if (percentage != 0) {
                percentagesByDirection.put(direction, percentage * 0.01);
            }
        }

 

이후에는 DFS를 통해 이동을 시작하는데, 이동할 때마다 해당 이동 방향별 확률을 누적하여 곱해주었고, 탐색을 마치면 즉, n번의 이동을 마치면 누적해서 곱했던 확률을 결과값에 더해줍니다.

 

참고로 탐색 시에 방문처리를 해주기 때문에 최종 탐색을 마친 경우에는 "이동 경로가 단순한 경우"만 해당됩니다.

 

전체 소스 코드

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

class Main {

    static int n, size;
    static double result = 0.0;
    static Map<String, Double> percentagesByDirection = new HashMap<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());

        // 동, 서, 남, 북
        String[] directions = {"EAST", "WEST", "SOUTH", "NORTH"};
        int percentage;
        for (String direction : directions) {
            percentage = Integer.parseInt(st.nextToken());
            if (percentage != 0) {
                percentagesByDirection.put(direction, percentage * 0.01);
            }
        }

        size = n * 2 + 1;

        boolean[][] visited = new boolean[size][size];
        visited[n][n] = true;
        move(n, n + 1, 1, 1.0, visited, "EAST");

        visited = new boolean[size][size];
        visited[n][n] = true;
        move(n, n - 1, 1, 1.0, visited, "WEST");

        visited = new boolean[size][size];
        visited[n][n] = true;
        move(n + 1, n, 1, 1.0, visited, "SOUTH");

        visited = new boolean[size][size];
        visited[n][n] = true;
        move(n - 1, n, 1, 1.0, visited, "NORTH");

        System.out.println(result);
    }

    public static void move(int x, int y, int depth, double percent, boolean[][] visited, String direction) {
        if (x < 0 || x > size - 1 || y < 0 || y > size -1 || !percentagesByDirection.containsKey(direction) || visited[x][y]) {
            return;
        }

        percent *= percentagesByDirection.get(direction) * 1000000000 / 1000000000.0;

        if (depth == n) {
            result += percent;
            return;
        }

        visited[x][y] = true;
        depth++;

        move(x + 1, y, depth, percent, visited, "SOUTH");
        move( x - 1, y, depth, percent, visited, "NORTH");
        move( x, y + 1, depth, percent, visited, "EAST");
        move( x, y - 1, depth, percent, visited, "WEST");

        visited[x][y] = false;
    }
}

 

참고자료

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