[백준/BOJ] 5014번: 스타트링크

문제

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

5014번: 스타트링크

해설

bfs를 연습하기에 좋은 문제라고 생각된다.

첨에 방문여부처리할 배열의 크기를 어떻게 정할까 고민을 했었는데, 엘레베이터는 건물의 최고층 이후로는 올라갈 수 없으므로 전체 층수 + 1만큼을 배열의 크기로 저장하면 되는 것이었다.

bfs를 수행할 큐에는 현재 층수, 움직인 횟수 정보를 담는다.

현재 층수에서 움직일 수 있는 방법은 2가지가 있다. U버튼을 통해 올라가거나, D버튼을 통해 내려가는 것이다.

따라서 현재 층수에서 각각의 값을 계산했을 때, 건물의 층수(1~F)의 범위에서 벗어나지 않고, 아직 방문하지 않았던 층이라면, 큐에 저장해주면 된다. 

현재 층수가 스타트링크가 있는 층수와 같아진다면, 그때의 움직인 횟수를 반환해주면 된다. 

코드

import java.util.*

private lateinit var visited: BooleanArray

data class MoveInfo(val floor: Int, val cnt: Int)

fun main() = with(System.`in`.bufferedReader()) {
    val st = StringTokenizer(readLine())
    val totalFloor = st.nextToken().toInt()
    val curFloor = st.nextToken().toInt()
    val startLinkFloor = st.nextToken().toInt()
    val up = st.nextToken().toInt()
    val down = st.nextToken().toInt()

    visited = BooleanArray(totalFloor + 1)
    val move = bfs(totalFloor, curFloor, startLinkFloor, up, down)

    if(move == -1) println("use the stairs")
    else println(move)
}

private fun bfs(totalFloor: Int, floor: Int, startLinkFloor: Int, up: Int, down: Int): Int {
    val que: Queue<MoveInfo> = LinkedList()
    que.add(MoveInfo(floor, 0))
    visited[floor] = true

    while(que.isNotEmpty()) {
        val cur = que.poll()
        val curFloor = cur.floor
        val curMoveCnt = cur.cnt

        if(curFloor == startLinkFloor) return curMoveCnt

        val upFloor = curFloor + up
        val downFloor = curFloor - down

        if(isCheck(upFloor, totalFloor)) {
            visited[upFloor] = true
            que.add(MoveInfo(upFloor, curMoveCnt + 1))
        }

        if(isCheck(downFloor, totalFloor)) {
            visited[downFloor] = true
            que.add(MoveInfo(downFloor, curMoveCnt + 1))
        }
    }

    return -1
}

private fun isCheck(floor: Int, totalFloor: Int): Boolean = (floor in 1 .. totalFloor && !visited[floor])