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

출처: unsplash.com

 

특정 거리의 도시 찾기(18352번)

Silver 2

#그래프 이론 #그래프 탐색 #너비 우선 탐색 #최단 경로 #데이크스트라

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

 

문제 내용

 

 

문제 접근

도시의 개수, 도로의 개수, 구해야 하는 최단 거리와 시작 지점이 주어질 때, 시작 지점 도시에서 다른 도시로 이동하는 최단 거리가 입력받은 최단 거리와 같은 도시 번호만 출력한다. 조건에 맞는 도시가 없으면 -1을 출력.

 

도시는 모두 1~N까지가 있다. 도로의 길이는 모두 1일 때, 최단 경로 입력값을 K라고 할 때, 출발 도시에서 각 도시로 이동하는 최단 경로가 K와 같은 도시만 출력한다.

bfs를 사용하면 된다.

 

bfs를 쓰기 위해서는 어쨌든 그래프가 있어야 한다.

4 4 2 1
1 2
1 3
2 3
2 4

 

이 입력 예제로 어떻게 그래프를 구성해야 할까?

그래프는 각 도시에 연결되어 있는 다른 도시들의 정보들을 저장하는 형태로 구성하면 된다.

위의 입력 예제를 기준으로는

1. 도시 1에는 2, 3
2. 도시 2에는 3, 4
3. 도시 3은 없음
4. 도시 4는 없음

다음과 같이 그래프를 구성해 줄 수 있다.

사진 1-1, 입력 예제 1의 구조

그러면 사진 1-1의 결과를 2중 list로 나타낼 수 있다.

도로의 방향이 단방향이다. 한 번 떠난 도시는 다시는 방문하면 방문할 수 없어야 한다. 다시 방문할 수 있으면 최단 거리가 아니게 되기 때문이다.

예를 들어 1 -> 3으로 거리가 1인 경우와 1 -> 2 -> 3으로 거리가 2인 경우 총 2개가 있는데 도시 3으로 가는 최단 경로는 1이 되어야 한다. 그래서 재방문을 막아 주어야 한다.

 

 

문제 해결 코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.LinkedList
import java.util.Queue

private var cities = arrayOf(mutableListOf<Int>())
private var visited = booleanArrayOf()
private val answer = mutableListOf<Int>()

private var city = 0
private var road = 0
private var minDistance = 0

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val input = readLine().split(" ").map { it.toInt() }
    val start = input[3]

    city = input[0]
    road = input[1]
    minDistance = input[2]
    cities = Array(city + 1) { mutableListOf() }
    visited = BooleanArray(city + 1)

    for (i in 0 until road) {
        val roadInfo = readLine().split(" ").map { it.toInt() }
        val roadStart = roadInfo[0]
        val roadEnd = roadInfo[1]
        cities[roadStart].add(roadEnd)
    }

    bfs(start)

    answer.sort()
    if (answer.isEmpty()) println(-1)
    else println(answer.joinToString("\n"))
}

private fun bfs(start: Int) {
    val queue: Queue<List<Int>> = LinkedList()
    queue.add(listOf(start, 0))
    visited[start] = true

    while (queue.isNotEmpty()) {
        val data = queue.poll()
        val beforeCity = data[0]
        val currentDistance = data[1]

        if (currentDistance == minDistance) answer.add(beforeCity)

        for (i in cities[beforeCity]) {
            if (!visited[i]) {
                visited[i] = true
                queue.add(listOf(i, currentDistance + 1))
            }
        }
    }
}

 

문제 풀이

그래프를 cities로 정의하고 입력받으면서 그래프를 정의하고 방문 여부도 visited로 설정해 준다.

visited를 2중 리스트로 설정하지 않은 이유는 현재 도시의 방문 여부만 판단하면 되기 때문에 2중 리스트로 구성할 필요가 없어서 이다.

bfs를 사용해서 각 도시 간의 최단 거리를 구해준다.

우선 시작 도시는 최단 거리가 0이기 때문에, queue에 도시 번호와 0을 저장한다. 이제 0이 1씩 더해지면서 최단 경로를 구하게 될 것이다.

이전 도시에서 다음 도시로 갈 수 있는 모든 경로를 for문으로 탐색하고 방문하지 않은 도시일 때만 queue에 넣어 주는 작업을 진행한다.

그리고 queue에서 꺼내온 값의 최단 경로가 현재 우리가 구해야 하는 최단 경로인 minDistance와 일치한다면 answer에 추가한다.

answer는 bfs가 끝나고 sort 해서 출력한다. answer가 비어 있으면 -1을 출력한다.

 

 

문제 해결 과정

평범한 bfs 문제, 원래는 데이크스트라 알고리즘 연습 문제였던 것 같지만, 잘 알지도 못하는데 내가 아는 걸로 풀어야지 어쩌겠는가?

데이크스트라 알고리즘은 일단 기억해 두었다가 나중에 따로 공부를 해볼까?

난이도 자체는 무난했다. bfs로 풀 수 있다는 것이 좋았다.