[백준 5214번] [Kotlin] 환승

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

5214번: 환승

 

난이도 : 골드 2
태그 : 그래프 이론, 그래프 탐색, 너비 우선 탐색

 

 

 

설명

몇 개의 역이 튜브로 연결되어 있고,

1번에서 N번까지 가는데 거쳐야 하는 최소 역 개수를 찾는 문제입니다.

 

 

 

시도 1

음... 각 튜브들끼리 연결되있다고 하니까,

단순히 각 튜브들끼리 모든 순서쌍을 그래프를 만들면 풀리지 않을까요?

 

(1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000) 범위를 다시 보니 메모리가 터질만 했네요.

최악의 경우 대략 1000^3 = 1,000,000,000개 간선이 생길 수 있습니다...

역시나 쉽게 풀릴리가 없었습니다.

 

 

 

시도 2

 

 

하이퍼튜브도 정점으로 생각해,

총 노드의 개수를 역 개수 + 하이퍼튜브 개수로 설정합니다.

예제에서 9개 역, 3개 노드가 있는데,

정점의 개수는 총 12개로, 1 ~ 9까지는 역, 10 ~ 12는 하이퍼튜브로 사용합니다.

 

 

 

 

위와 같이, 하이퍼튜브로 연결된 노드들을 하이퍼튜브와 연결합니다.

위와 같이 각 역들을 하이퍼튜브로 엮게 될 경우

최악의 경우 1000^2 = 1,000,000개 간선으로,

1000^3 = 1,000,000,000개에 비하면 꽤 줄였습니다.

 

위 그림과 같이 해당 방식에서는 역에서 다른 역을 가려면 튜브를 거쳐야 합니다.

역 -> 튜브 -> 역 -> 튜브 -> 역 -> 튜브와 같은 방식으로 역과 튜브를 번갈아가며 이동하죠.

따라서 1부터 N까지 역 이동 횟수 = 총 이동 횟수 / 2 + 1이 정답이 됩니다.

 

 

 

 

소스코드

import java.util.*

fun main() = with(System.`in`.bufferedReader()) {
    // n: 역 개수, k : 하이퍼 튜브가 연결하는 역 개수, m : 하이퍼 튜브 개수
    val (n, k, m) = readLine().split(" ").map { it.toInt() }

    val graph = Array(n + m + 1) { mutableListOf<Int>() }

    repeat(m) { i ->
        val st = StringTokenizer(readLine())
        repeat(k) { j ->
            val node = st.nextToken().toInt()
            // 해당 역(node)와 튜브(n+i+1)을 연결함.
            graph[node].add(n + i + 1)
            graph[n + i + 1].add(node)
        }
    }

    val visited = IntArray(n + m + 1)
    val q = LinkedList<Int>() as Queue<Int>
    visited[1] = 1
    q.offer(1)

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

        if (target == n) {
            println(visited[target] / 2 + 1)
            return
        }

        graph[target].forEach { next ->
            if (visited[next] != 0) return@forEach

            visited[next] = visited[target] + 1
            q.offer(next)
        }
    }

    println(-1)
}

 

 

 

 

후기

쉽게 생각했다가, 생각보다 매운맛에 당황한 문제였던 것 같습니다.