백준 5214 환승 Kotlin (bfs)

문제 출처 : https://www.acmicpc.net/problem/5214

5214번: 환승

문제

아주 먼 미래에 사람들이 가장 많이 사용하는 대중교통은 하이퍼튜브이다. 하이퍼튜브 하나는 역 K개를 서로 연결한다. 1번역에서 N번역으로 가는데 방문하는 최소 역의 수는 몇 개일까?

입력

첫째 줄에 역의 수 N과 한 하이퍼튜브가 서로 연결하는 역의 개수 K, 하이퍼튜브의 개수 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000)

다음 M개 줄에는 하이퍼튜브의 정보가 한 줄에 하나씩 주어진다. 총 K개 숫자가 주어지며, 이 숫자는 그 하이퍼튜브가 서로 연결하는 역의 번호이다. 

출력

첫째 줄에 1번역에서 N번역으로 가는데 방문하는 역의 개수의 최솟값을 출력한다. 만약, 갈 수 없다면 -1을 출력한다.

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

풀이

2021.08.19 - [알고리즘 문제 풀이/백준] - 백준 2021 최소 환승 경로 c++,Kotlin (bfs)

위의 문제와 비슷한 문제이다.

우선 입력을 해석하면,

15 8 4

11 12 8 14 13 6 10 7

1 5 8 12 13 6 2 4

10 15 4 5 9 8 14 12

11 12 14 3 5 6 1 13

역은 총 1부터 15까지,

각 하이퍼튜브마다 연결된 역의 개수 8

하이퍼튜브의 개수 4이다.

찾는 값은 1번 역에서 15(n)번 역으로 가는데 방문하는 최소 역의 수이므로, 방문 순서는 다음과 같다.

1. 2번째 하이퍼튜브의 1번 역

2. 3번째 하이퍼튜브의 5번 역

3. 3번째 하이퍼튜브의 15번 역

1->5>15로 최소 3개의 역을 방문해야 한다. //최소 역이 나오는 순서는 여러 개 있을 수 있다.

이를 구하기 위한 풀이는 다음과 같다.

 

1. i번 역을 지나는 하이퍼튜브들을 저장하는 그래프A 생성, j번 하이퍼튜브가 지나는 역들을 저장하는 그래프B를 생성

 -본인은 두 개의 그래프를 하나로 만들었고, 이를 최대 역의 개수(n)보다 작은 인덱스에 그래프A를 저장하였고,

  최대 역의 개수보다 큰 인덱스에 그래프B를 저장하였다.

2. 해당 역에 도착하는데 방문한 역의 수를 저장할 visited[역] 배열을 만든다.

3. 1(출발 역)의 vsited[1]에 1을 저장한다.

4. 1(출발 역)부터 bfs를 시작하여 다음 방문할 인덱스가 역이라면 visted[다음(역)] = visited[현재]+1 해주고,

   다음 방문할 인덱스가 호선이라면 visited[다음(호선)] = visited[현재] 해준다.

5. 3번 과정을 반복하며 도착 역에 방문하면 visited[현재] + 1(마지막 역도 개수에 추가)을 리턴한다.

6. 도착 역에 방문하지 못하고 bfs가 종료된다면 -1을 출력한다.(도착 역에 방문할 수 없는 경우)

 

하이퍼 튜브의 개수(m)가 역의 개수(n)보다 작다는 보장이 없다는 것과,

1 1 1

1

의 입력을 주의하자!

코드

import java.util.*
fun bfs(graph : Array<MutableList<Int>>, visited : IntArray , n : Int) : Int{
    val q : Queue<Int> = LinkedList<Int>()
    q.add(1)
    visited[1]=1
    while(q.isNotEmpty()){
        val cur = q.poll()
        if(cur==n) return visited[cur]
        for(i in graph[cur].indices){
            val next = graph[cur][i]
            if(visited[next]>0) continue
            if(next == n){
                return visited[cur]+1
            }
            else if(next<n){
                visited[next] = visited[cur]+1
            }
            else{
                visited[next] = visited[cur]
            }
            q.add(next)
        }
    }
    return -1
}


fun main() = with(System.out.bufferedWriter()){
    val br= System.`in`.bufferedReader()
    var tk = StringTokenizer(br.readLine())
    val (n,k,m) = List(3){Integer.parseInt(tk.nextToken())}
//    val tube = Array(m+1,{IntArray(k,{0})})
    val graph = Array(200001,{mutableListOf<Int>()})
    val visited = IntArray(200001,{0})
    for(i in 1 .. m){
        tk = StringTokenizer(br.readLine())
        for(j in 0 until k){
            val num = Integer.parseInt(tk.nextToken())
            graph[num].add(n+i)
            graph[n+i].add(num)
        }
    }
    write("${bfs(graph,visited,n)}")
    close()
}