[알고리즘] 백준 1405 미친 로봇 -DFS, 완전탐색- 자바 코틀린

 

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

1405번: 미친 로봇

 

 

백준 완전탐색 유형에서 미친 로봇이라는 문제를 풀어보았습니다. ㅎㅎ

동서남북으로 움직일 수 있는 로봇이 N만큼 이동을 하는데 로봇이 같은 곳을 한 번보다 많이 움직이지 않을 때 이동경로가 단순한 로봇이고 이러한 움직임을 가질 확률을 구하는 문제였습니다. 추가로 동서남북 이동확률이 존재합니다.

그래서 풀이방법은 움직임과 해당 경로까지 움직임의 확률을 DFS로 넘기면서 탐색해주면 되는 문제였습니다.

 

주석으로 풀이를 적어놨습니다. 

풀이는 다음과 같습니다. 

 

[Java]

import java.util.Scanner;

class Main {
    private static int N; // 로봇 움직일 횟수
    private static double[] directions = new double[4]; // 각 방향의 이동확률 (동서남북순)
    private static int[] dr = {1, -1, 0, 0}; // 동서남북순으로 directions 와 맞춰준다. 안그럼 틀림
    private static int[] dc = {0, 0, 1, -1};
    private static boolean[][] isVisited = new boolean[100][100];
    private static double answer = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        for (int i = 0; i < 4; i++) { // 각 방향 이동 확률 초기화  (이동할 확률을 모두 더하면 100이다.)
            directions[i] = 0.01 * sc.nextInt();
        }
        isVisited[50][50] = true;
        dfs(50, 50, 1.0);
        System.out.println(answer);
    }

    private static void dfs(int r, int c, double p) {
        if (N == 0) { // 다움직임
            answer += p; // 로빗의 이동경로 단순할 확률업
            return;
        }
        for (int i = 0; i < 4; i++) {
            int r2 = r + dr[i];
            int c2 = c + dc[i];
            if (!isVisited[r2][c2] && directions[i] > 0) { // 0인 이동확률도 제외해줘야함
                N--;
                isVisited[r2][c2] = true;
                dfs(r2, c2, p * directions[i]);  // 이동 , 확률 더해줌
                N++;
                isVisited[r2][c2] = false;
            }
        }
    }

}

 

[Kotlin]

import java.util.*


private var N // 로봇 움직일 횟수
        = 0
private val directions = DoubleArray(4) // 각 방향의 이동확률 (동서남북순)
private val dr = intArrayOf(1, -1, 0, 0) // 동서남북순으로 directions 와 맞춰준다. 안그럼 틀림
private val dc = intArrayOf(0, 0, 1, -1)
private val isVisited = Array(100) { BooleanArray(100) }
private var answer = 0.0


fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    N = sc.nextInt()
    for (i in 0..3) { // 각 방향 이동 확률 초기화  (이동할 확률을 모두 더하면 100이다.)
        directions[i] = 0.01 * sc.nextInt()
    }
    isVisited[50][50] = true
    dfs(50, 50, 1.0)
    println(answer)
}

private fun dfs(r: Int, c: Int, p: Double) {
    if (N == 0) { // 다움직임
        answer += p // 로빗의 이동경로 단순할 확률업
        return
    }
    for (i in 0..3) {
        val r2 = r + dr[i]
        val c2 = c + dc[i]
        if (!isVisited[r2][c2] && directions[i] > 0) { // 0인 이동확률도 제외해줘야함
            N--
            isVisited[r2][c2] = true
            dfs(r2, c2, p * directions[i]) // 이동 , 확률 더해줌
            N++
            isVisited[r2][c2] = false
        }
    }
}

https://github.com/mtjin/algorithm_practice/commit/150893e838f243c517a6c26f7137827d5f83134c

백준 1405 풀이 · mtjin/algorithm_practice@150893e

 

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다. !!!