[백준 18352번] [Kotlin] 특정 거리의 도시 찾기

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

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

 

난이도 : 실버 2
태그 : 그래프 이론, 그래프 탐색, 너비 우선 탐색, 데이크스트라

 

 

설명

한 도시에서 거리가 k인 도시를 찾는 문제입니다.

너비 우선 탐색을 사용하거나,

한 점에서 다른 모든 점까지의 최단거리를 구하는 다익스트라를 사용해도 될 것 같네요.

저는 너비 우선 탐색을 통해 풀이하였습니다.

 

 

소스코드

import java.util.*

fun main() = with(System.`in`.bufferedReader()) {
    // n 도시의 수, m 간선의 수, k 최단거리, x 출발 도시 번호
    val (n, m, k, x) = readLine().split(" ").map { it.toInt() }
    val visited = Array(n + 1) { -1 }
    val connected = Array(n + 1) { ArrayList<Int>() }

    repeat(m) {
        val st = StringTokenizer(readLine())
        connected[st.nextToken().toInt()].add(st.nextToken().toInt())
    }

    val q = LinkedList<Int>() as Queue<Int>
    q.offer(x)
    visited[x] = 0

    while (q.isNotEmpty()) {
        val target = q.poll()

        for (next in connected[target]) {
            if (visited[next] == -1) {
                q.offer(next)
                visited[next] = visited[target] + 1
            }
        }
    }

    val sb = StringBuilder()
    for (i in 1..n) if (visited[i] == k) sb.append(i).append("\n")

    print(sb.ifEmpty { "-1" })
}

 

코드분석

1. 방문여부를 체크할 visited, 한 점을 기준으로, 연결되어있는 점들의 정보를 담을 connected 생성
2. 시작점의 visited 값을 0으로 갱신하고 큐에 시작점을 삽입
3. BFS 시작
   1. 큐에서 값 하나를 빼고, 연결되어있는 노드를 하나씩 탐색
   2. 연결되지 않은 노드 중, 방문하지 않은 노드(visited != -1)를 찾아 visited 값을 방금 큐에서 꺼낸 값 +1으로 갱신
   3. 해당 노드를 큐에 삽입
   4. 큐가 빌 때까지 3-1 과정을 반복
4. visited의 값 중, k인 것을 찾아 출력하고, 만약 그러한 값이 없으면 -1을 출력

 

 

후기

문제를 보자마자 BFS가 딱 떠올라 BFS를 사용하여 문제를 풀이하였는데,

문제 태그의 다익스트라를 보고 나니, 생각해보니 다익스트라로도 풀 수 있겠다는 생각이 들었습니다.

다익스트라를 사용해서도 한 번 풀어봐야겠습니다.