[백준] 18352번: 특정 거리의 도시 찾기 - Kotlin[코틀린]

문제

 

18352번: 특정 거리의 도시 찾기

 

---

풀이

 

 주어진 도로와 도시 정보에서 모든 도시간의 거리가 1이라는 점을 이용해 너비 우선 탐색(BFS)으로 해결할 수 있다.

 

 시작 도시로부터 BFS를 수행하며 거리를 계산하고 거리 배열에 저장해준다. 여기서 모든 도시간의 거리가 1이기 때문에 도시에 처음 도착했을 때의 거리가 최단 거리일 것이다. 탐색이 끝난 후 찾으려는 거리에 도시가 있다면 도시를 출력해주고, 없다면 -1을 출력한다.

 

---

코드

 

import java.util.*

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val st = StringTokenizer(br.readLine())
    val city = st.nextToken().toInt()
    val road = st.nextToken().toInt()
    val street = st.nextToken().toInt()
    val first = st.nextToken().toInt()

    val distance = IntArray(city + 1){ -1 }
    val graph = ArrayList<ArrayList<Int>>()
    repeat(city+1){ graph.add(ArrayList()) }
    repeat(road) {
        with(StringTokenizer(br.readLine())) {
            graph[nextToken().toInt()].add(nextToken().toInt())
        }
    }

    fun bfs() {
        val queue : Queue<Int> = LinkedList()
        queue.offer(first)
        while (queue.isNotEmpty()) {
            val now = queue.poll()
            for(next in graph[now]) {
                if(distance[next] == -1) {
                    distance[next] = distance[now] + 1
                    queue.add(next)
                }
            }
        }
    }

    distance[first] = 0
    bfs()

    val sb = StringBuilder()
    var check = false
    for(i in 1 .. city) {
        if(distance[i] == street) {
            check = true
            sb.append("$i\n")
        }
    }

    bw.write(if(check) sb.toString() else "-1")
    bw.flush()
    bw.close()
    br.close()
}