백준 15644번 구슬탈출3 Kotlin 구현해 보기

---

```

백준 15644번 구슬탈출3 Kotlin 구현해 보기

```

Kimc Kotlin Study

이번 글을 통해 배워갈 내용

1. 백준 15644번 풀이

---

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

15644번: 구슬 탈출 3

 

백준 15644번 제목은

판을 시뮬레이션하고

파란 구슬, 빨간 구슬, 구멍이 있을 때

판을 좌, 우, 상, 하로 움직여서

파란 구슬을 구멍에 넣지 않고

빨간 구슬을 구멍에 넣어주면 되는 문제입니다

 

빨간 구슬을 구멍 안에

넣을 수 있는 판의 움직임 횟수를 구해주면 됩니다

그리고 중간에 움직인 방향도 같이 출력해줍니다

 

구슬탈출 1, 2 을 먼저 풀고 오시면 쉽게 풀 수 있습니다
https://codemasterkimc.tistory.com/645

백준 13459번 구슬탈출 Kotlin 구현해보기

https://codemasterkimc.tistory.com/646

백준 13460번 구슬탈출2 Kotlin 구현해보기

 

---

30분 정도 위에 링크를 방문하셔서 풀어보시고

안 풀리시는 경우에만 아래 해답을 봐주시면 감사하겠습니다.

---

입력을 받고

정해진 조건에 맞춰서 계산을 해서 출력해 주면 되는

문제입니다.

 

fun main() {
    val inputDto = getInput()
    print(solution(inputDto))
}

fun getInput(): InputDto {
    val (rows, cols) = readLine()!!.split(" ").map { it.toInt() }
    val locationMap = Array(rows) { Array(cols) { ' ' } }
    val visitMap = Array(rows) { Array(cols) { Array(rows) { Array(cols) { false } } } }
    var rx = 0
    var ry = 0
    var bx = 0
    var by = 0

    val inputLines = List(rows) { readLine()!! }

    inputLines.forEachIndexed { rowIdx, line ->
        line.forEachIndexed { colIdx, char ->
            locationMap[rowIdx][colIdx] = char
            when (char) {
                'R' -> {
                    rx = rowIdx; ry = colIdx
                }

                'B' -> {
                    bx = rowIdx; by = colIdx
                }
            }
        }
    }

    return InputDto(Step(rx, ry, bx, by, 0, ""), locationMap, visitMap, "")
}

data class Step(
    var rx: Int,
    var ry: Int,
    var bx: Int,
    var by: Int,
    var count: Int,
    var dHistory: String
)

data class InputDto(
    val step: Step,
    val locationMap: Array<Array<Char>>,
    val visitMap: Array<Array<Array<Array<Boolean>>>>,
    var finalDHistory: String
) {
    private val dx = intArrayOf(1, -1, 0, 0)
    private val dy = intArrayOf(0, 0, 1, -1)
    private val d = charArrayOf('D', 'U', 'R', 'L')

    fun bfs(step: Step): Int {
        val q = ArrayDeque<Step>()
        q.add(step)
        visitMap[step.rx][step.ry][step.bx][step.by] = true

        while (q.isNotEmpty()) {
            val currentStep = q.removeFirst()
            val (rx, ry, bx, by, count, dHistory) = currentStep

            if (count >= 10) break

            for (i in 0 until 4) {
                var (nrx, nry, rc) = moveBall(rx, ry, i)
                var (nbx, nby, bc) = moveBall(bx, by, i)

                if (locationMap[nbx][nby] == 'O') continue
                if (locationMap[nrx][nry] == 'O') {
                    finalDHistory = dHistory + d[i].toString()
                    return count + 1
                }

                if (nrx == nbx && nry == nby) {
                    if (rc > bc) {
                        nrx -= dx[i]
                        nry -= dy[i]
                    } else {
                        nbx -= dx[i]
                        nby -= dy[i]
                    }
                }

                if (visitMap[nrx][nry][nbx][nby]) continue
                visitMap[nrx][nry][nbx][nby] = true
                q.addLast(Step(nrx, nry, nbx, nby, count + 1, dHistory + d[i].toString()))
            }
        }
        return -1
    }

    private fun moveBall(x: Int, y: Int, i: Int): Triple<Int, Int, Int> {
        var nx = x
        var ny = y
        var cnt = 0

        while (
            locationMap[nx + dx[i]][ny + dy[i]] != '#'
            && locationMap[nx][ny] != 'O'
        ) {
            nx += dx[i]
            ny += dy[i]
            cnt++
        }
        return Triple(nx, ny, cnt)
    }
}

fun solution(dto: InputDto): String {
    val steps = dto.bfs(dto.step)
    val directions = dto.finalDHistory

    return if (steps == -1) {
        "-1"
    } else {
        """$steps
$directions"""
    }


}

// https://codemasterkimc.tistory.com/

 

 

읽어주셔서 감사합니다

 

무엇인가 얻어가셨기를 바라며

 

오늘도 즐거운 코딩 하시길 바랍니다 ~ :)

 

---