[BOJ 실버2] 텔레포트 정거장 Kotlin

문제

풀이

• DP? BFS 고민중 DP로는 어려울것 같아 BFS + 인접리스트로 푸니 바로 풀렸습니다.

코드

import java.lang.Math.min
import java.util.*

lateinit var board : Array<ArrayList<Int>>
lateinit var visit : BooleanArray
lateinit var time : IntArray
fun main() = with(System.`in`.bufferedReader()){
    val (n,m) = readLine().split(" ").map{it.toInt()}
    val (s,e) = readLine().split(" ").map{it.toInt()}
    board = Array(300001){
        ArrayList()
    }
    time = IntArray(300001){Int.MAX_VALUE}
    visit = BooleanArray(300001){false}
    repeat(m){
        val t = readLine().split(" ").map{it.toInt()}
        board[t[0]].add(t[1])
        board[t[1]].add(t[0])
    }
    bfs(s,e)
    println(time[e])
}

fun bfs(start : Int, target : Int){
    val q = LinkedList<Int>()
    q.add(start)
    visit[start] = true
    time[start] = 0
    while(!q.isEmpty()){
        val t = q.poll()
        if(t==target){
            return
        }
        if(t>=1) {
            if(!visit[t-1]) {
                time[t - 1] = min(time[t - 1], time[t] + 1)
                q.add(t - 1)
                visit[t-1] = true
            }
        }
        if(t<300000) {
            if(!visit[t+1]) {
                time[t + 1] = min(time[t + 1], time[t] + 1)
                q.add(t + 1)
                visit[t+1] = true
            }
        }
        for(temp in board[t]){
            if(!visit[temp]) {
                time[temp] = min(time[temp], time[t] + 1)
                q.add(temp)
                visit[temp] = true
            }
        }
    }
}