[BOJ] 미친 로봇 in Python & Kotlin

문제풀러 가기!

단순 bfs였습니다.
중요한 것은 출력 값이 소수여야 하기 때문에 이부분만 조심하면 금방 풀 수 있었던 문제였습니다.

딱히 설명할게 없습니다... 문제에서 주어진 조건대로 방문한 곳은 다시 재방문하지 않으면서 모든 경우의 수를 구하고 해당 확률값을 더해주면 됩니다.

아 굳이 설명할게 있다면, 어차피 모두 N만큼 움직인 상태에서 확률값이 나오는 것이기 때문에 확률의 덧샘법칙이 성립합니다.

수학적인 이야기는 여기서 그만 둘게요.

어려운 내용도 아니고

어떤 고등학교 교육과정에서도 설명하는 내용이기 때문에 아! 하면서 금방 감이 오실겁니당

아래는 python 풀이입니다.

import sys
input = sys.stdin.readline

N, e, w, n, s = map(int, input().split())
visited = [[False for _ in range(31)] for _ in range(31)]

direct = [e, w, n, s]
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
probability = float(0)

def dfs(depth, prob, row, col):
    global probability

    if depth >= N:
        probability += prob
        return

    for i in range(4):
        nrow, ncol = row + dx[i], col + dy[i]
        if not visited[nrow][ncol] and direct[i] != 0:
            visited[nrow][ncol] = True
            dfs(depth+1, prob*direct[i]/100, nrow, ncol)
            visited[nrow][ncol] = False
    
visited[15][15] = True
dfs(0, 1, 15, 15)
print(probability)

아래는 kotlin 풀이입니다.

import java.io.BufferedReader
import java.io.InputStreamReader

private lateinit var visited: Array<BooleanArray>
private lateinit var direct: Array<Int>
var number: Int = 0
var probability: Double = 0.0
val movingX: Array<Int> = arrayOf(0, 0, 1, -1)
val movingY: Array<Int> = arrayOf(1, -1, 0, 0)

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val (N, e, w, n, s) = readLine().split(" ").map { it.toInt() }
    number = N
    visited = Array(31) { BooleanArray(31) { false } }
    direct = arrayOf(e, w, n, s)
    visited[15][15] = true
    crazyMoving(0, 1.0, 15, 15)
    println(probability)
}

fun crazyMoving(depth: Int, prob: Double, row: Int, col: Int) {

    if (depth >= number) {
        probability += prob
        return
    }

    for (i in 0 until 4) {
        var nRow = row + movingX[i]
        var nCol = col + movingY[i]
        if (!visited[nCol][nRow] && direct[i] != 0) {
            visited[nCol][nRow] = true
            crazyMoving(depth+1, prob*direct[i]/100, nRow, nCol)
            visited[nCol][nRow] = false
        }
    }
}