백준 1405 미친 로봇 Kotlin (백트래킹)

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

1405번: 미친 로봇

문제

통제 할 수 없는 미친 로봇이 평면위에 있다. 그리고 이 로봇은 N번의 행동을 취할 것이다.

각 행동에서 로봇은 4개의 방향 중에 하나를 임의로 선택한다. 그리고 그 방향으로 한 칸 이동한다.

로봇이 같은 곳을 한 번보다 많이 이동하지 않을 때, 로봇의 이동 경로가 단순하다고 한다. (로봇이 시작하는 위치가 처음 방문한 곳이다.) 로봇의 이동 경로가 단순할 확률을 구하는 프로그램을 작성하시오. 예를 들어, EENE와 ENW는 단순하지만, ENWS와 WWWWSNE는 단순하지 않다. (E는 동, W는 서, N은 북, S는 남)

입력

첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고,  모든 확률은 100보다 작거나 같은 자연수 또는 0이다. 그리고, 동서남북으로 이동할 확률을 모두 더하면 100이다.

확률의 단위는 %이다.

출력

첫째 줄에 로봇의 이동 경로가 단순할 확률을 출력한다. 절대/상대 오차는 10-9 까지 허용한다.

알고리즘 분류

• 수학
• 그래프 이론
• 브루트포스 알고리즘
• 그래프 탐색
• 깊이 우선 탐색
• 백트래킹
• 확률론

풀이

4 30 30 20 20

위 예시에서 우선 세 번째 이동까지 ENW로 이동했다고 해보자.

첫 번째 이동에선 EWSN 모두 이동할 수 있다.

두 번째 이동에선 W로 이동하는 경우를 제외한 3가지 방향으로 이동 가능하다.

세 번째 이동에선 S로 이동하는 경우를 제외한 3가지 방향으로 이동 가능하다.

네 번째 이동에선 E,S로 이동하는 경우를 제외한 2가지 방향으로 이동 가능하다.

 

각 턴마다 이동할 수 있는 방향은 더해야 함을 의미하고, 다음 턴은 이전 턴의 확률에 곱해야 함을 의미한다.

첫 번째 이동에서 EWSN 모두 이동할 수 있기 때문에 최종적으로 E -> ?, W -> ?, S -> ?, N -> ? 4가지 확률을 더해주어야 한다.

E -> ?은 어떻게 구할 수 있을까?

E ->에서는 (두 번째 이동) E,N,W로 이동할 수 있다. 이 세 가지 방향 모두 이동해 보면 된다.

이렇게 가능한 방향으로 계속 이동하다가 n번만큼 이동했다면 n번만큼 이동했을 때 해당 루트가 만들어지기까지의 확률을 누적해주면 된다.

 

위 예시에서 ENW?로 이동하는 확률을 구해보자.

첫 번째 이동 E : 0.3

두 번째 이동 N : 0.2

세 번째 이동 W : 0.3

네 번째 이동은 N, W로 이동 가능

네 번째 이동 N : 0.2

네 번째 이동 W : 0.3

즉 ENW?는 ENWN + ENWW로 0.3*0.2*0.3*0.2 + 0.3*0.2*0.3*0.3이다.

이동할 수 있는지 없는지 가지치는 것은 2차원 visited 그래프를 활용했다.

  

 

코드

val br = System.`in`.bufferedReader()
fun getIntList() = br.readLine().trim().split(' ').map { it.toInt() }

val dir = arrayOf(
    arrayOf(0, 1),
    arrayOf(0, -1),
    arrayOf(1, 0),
    arrayOf(-1, 0)
)
var result = 0.0
var t = 0
var E = 0
var W = 0
var S = 0
var N = 0
fun main() = with(System.out.bufferedWriter()) {
    //input
    with(getIntList()) {
        t = get(0)
        E = get(1)
        W = get(2)
        S = get(3)
        N = get(4)
    }
    val visited = Array(100) { BooleanArray(100) }
    //solve
    dfs(0, 1.0, 50, 50, visited, t)
    //output
    write("$result")
    close()
}

fun Int.dirPer(): Double {
    return when (this) {
        0 -> E / 100.0
        1 -> W / 100.0
        2 -> S / 100.0
        else -> N / 100.0
    }
}

fun dfs(cnt: Int, per: Double, r: Int, c: Int, visited: Array<BooleanArray>, t: Int) {
    if (cnt == t) {
        result += per
        return
    }
    visited[r][c] = true
    for (i in 0 until 4) {
        val nr = r + dir[i][0]
        val nc = c + dir[i][1]
        if (visited[nr][nc]) continue
        dfs(cnt + 1, per * i.dirPer(), nr, nc, visited, t)
    }
    visited[r][c] = false
}