250x250
06-26 09:54
관리 메뉴

막내의 막무가내 프로그래밍 & 일상

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

알고리즘/DFS, BFS, 시뮬, 백트래킹

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

막무가내막내 2021. 8. 9. 16:59
300x250
SMALL

 

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

 

1405번: 미친 로봇

첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고,  모든 확률은 100보다 작거나 같은 자

www.acmicpc.net

 

 

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

동서남북으로 움직일 수 있는 로봇이 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

Permalink This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository. Showing 2 changed files with 80 additions and 0 deletions. +40 −0 백준 1405 미친 로봇 -DFS, 완전탐색-/Main.java +40 −0

github.com

 

 

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

 

 

 

 

 

300x250
LIST
"이 포스팅은 쿠팡 파트너스 활동의 일환으로, 이에 따른 일정액의 수수료를 제공받습니다."
0 Comments
댓글쓰기 폼