백준 - 미친 로봇(Kotlin)

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.

https://github.com/ROUTINE-STUDY/Algorithm

 

저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능

문의는 댓글 바람.

 

문제 출처 :https://www.acmicpc.net/problem/1405

 

[문제 설명]

로봇이 이동한다. 이 때, 사이클이 있으면 미친 경로. 없으면 정상적인 경로다.

정상적인 경로를 구하라.

 

[접근 방법]

로봇이 이동할 때마다 확률을 계산해주는 DFS 방식으로 풀었습니다.

만약 로봇이 방문했던 좌표를 방문하지 않고, N번 모두 성공적으로 이동할 수 있다면 성공하여 전체 확률에 현재 확률을 더해줍니다.

 

처음에 이 아이디어를 바로 떠올리기는 했는데, 시간복잡도 계산을 실수해서 다른 방법을 계속 찾은 문제입니다.

4방향으로 계속 이동한다고 생각해서 시간복잡도가 O(4^N)로 계산해서 시간 초과가 날 줄 알았습니다.

곰곰이 다시 생각해보니 갔던 방향은 재귀를 부르지 않으므로 방향 이동은 3방향으로만 일어납니다.

따라서 시간복잡도는 O(3^N) = O(3^14) = 4782969이므로 굉장히 여유가 있었습니다.

 

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

// 동 서 남 북 이동벡터
val directions = arrayOf(intArrayOf(0, 1), intArrayOf(0, -1), intArrayOf(1, 0), intArrayOf(-1, 0))
// 동 서 남 북 각각 확률
val possibles = DoubleArray(4)
// 지도
val map = Array(30) { BooleanArray(30) }
// 이동횟수
var N = 0
// 모든 확률의 총합
var answer = 0.0
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val input = readLine().split(" ")
    N = input[0].toInt()
    for (i in 1..4) {
        possibles[i - 1] = input[i].toDouble() / 100
    }

    map[15][15] = true
    backtracking(currentY = 15, currentX = 15, moveCnt = 0, currentPossible = 1.0)
    println(answer)
}

fun backtracking(currentY: Int, currentX: Int, moveCnt: Int, currentPossible: Double) {
    if (moveCnt == N) {
        answer += currentPossible
        return
    }

    for (dIdx in directions.indices) {
        val nextY = currentY + directions[dIdx][0]
        val nextX = currentX + directions[dIdx][1]
        // 방문했던 좌표거나 확률이 0이라 이동할 수 없는 좌표면 이동 안함.
        if (map[nextY][nextX] || possibles[dIdx] == 0.0) {
            continue
        }
        map[nextY][nextX] = true
        backtracking(currentY = nextY, currentX = nextX, moveCnt = moveCnt + 1, currentPossible * possibles[dIdx])
        map[nextY][nextX] = false
    }
}