[BOJ 실버2] 촌수계산 Kotlin

문제

풀이

  • 인접리스트 + BFS 풀이

코드

import java.util.*
import kotlin.collections.ArrayList


fun main(args: Array<String>) = with(System.`in`.bufferedReader()){
    var n = readLine().toInt()
    var (start,target) = readLine().split(" ").map{it.toInt()}
    var case = readLine().toInt()
    var list = Array(n+1){
        ArrayList<Int>()
    }
    repeat(case){
        val (a,b) = readLine().split(" ").map{it.toInt()}
        list[a].add(b)
        list[b].add(a)
    }
    var ans = bfs(list,start,target)
    println(if(ans==n+1) -1 else ans)
}

fun bfs(list: Array<ArrayList<Int>>, start: Int, target: Int) : Int {
    val q = LinkedList<Int>()
    val visit = BooleanArray(list.size){false}
    q.add(start)
    visit[start]= true
    var dist= IntArray(list.size){list.size}
    dist[start] = 0
    while(!q.isEmpty()){
        val cur = q.poll()
        if(cur==target){
            break
        }
        for(t in list[cur]){
            if(!visit[t]){
                q.add(t)
                dist[t] = dist[cur]+1
                visit[t] = true
            }
        }
    }
    return dist[target]
}

좋은 웹페이지 즐겨찾기