백준 22868 산책 (small) Kotlin (bfs)

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

22868번: 산책 (small)

문제

코로나로 인하여 확찐자가 되버려 오늘부터 산책을 하려고 한다. 산책할 경로를 정하려고 한다.

현재 있는 곳 S에서 출발하여 S와 다른 곳인 E를 찍고 다시 S로 돌아오는 경로로 만들려고 한다. 산책을 할 때 이미 갔던 정점을 또 가기 싫어 E에서 S로 올 때 S에서 E로 간 정점을 제외한 다른 정점으로 이동하려고 한다. 또한 산책 거리가 긴 것을 싫어하여 S에서 E로 가는 짧은 거리와 E에서 S로 가는 짧은 거리를 원한다.

정점 S에서 정점 E로 이동할 때, 짧은 거리의 경로가 여러개 나올 수 있다. 그 중, 정점 S에서 정점 E로 이동한 경로를 나열했을 때, 사전순으로 가장 먼저 오는 것을 선택한다.

예를 들어, 정점 1에서 정점 2로 이동한다고 했을 때, 짧은 거리의 경로가 1 4 3 2와 1 3 4 2가 있다고 가정을 해보자. 두 개의 경로중 사전순으로 먼저 오는 것은 1 3 4 2이므로 정점 1에서 정점 2로 가는 최단 경로 중 두 번째 것을 선택한다.

이와 같이 산책 경로를 정할 때, 산책 전체 경로의 거리(S에서 E로 가는 거리 + E에서 S로 가는 거리)를 구해보자.

입력

첫 번째 줄에는 정점의 개수 N과 두 정점 사이를 잇는 도로의 개수 M이 공백으로 구분되어 주어진다.

두 번째 줄부터 M+1번째 줄까지 정점 A,B가 공백으로 구분되어 주어진다. 정점 A와 정점 B 사이의 거리는 항상 1이다. 이때, 정점 A와 정점 B는 양방향으로 이동해도 된다.

정점 A와 정점 B를 잇는 도로는 두개 이상 주어지지 않는다.

 M+2번째 줄에는 정점 S와 정점 E가 공백으로 구분되어 주어진다.

산책을 할 수 있는 경로가 있는 데이터만 주어진다.

출력

산책의 전체 경로의 길이를 출력한다.

제한

알고리즘 분류

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

풀이

S->E, E->S 두 번의 BFS를 돌려야 하는 그래프 탐색 문제이다.

우선 S->E 경로의 최단 거리와, 여러 개의 최단 거리 중 사전 순으로 가장 앞에 오는 경로를 구해야 한다.

 

1. 말 그대로 여러 개의 최단 거리를 구해서 사전 순으로 가장 앞에 오는 경로를 구하는 방법,

2. 애초에 처음 구해지는 최단 거리를 사전 순으로 가장 앞에 오는 경로로 만드는 방법이 있다.

 

여러 개의 최단 거리 중 사전 순으로 앞에 오는 경로를 구하는 방법은 여러 개의 최단 거리를 구하는 것도 오래 걸리고,

최단 거리가 구해질 때마다, 사전순으로 비교를 해야 하기 때문에 오래 걸린다.

애초에 최단 거리를 사전 순으로 앞서게 만드는 방법은, 처음 입력받은 그래프를 오름차순으로 정렬하면 bfs로 처음 찾은 최단 거리가 사전 순으로 가장 앞선 경로가 된다.

두 방법 모두 통과는 되지만, 2번 방법이 훨씬 빠르게 동작한다.

 

위에서 구한 S->E의 최단 거리를 최종 리턴 값인 answer에 더해주고, 최단 거리의 경로를 그래프에서 삭제한다.

이는 visited배열에 true를 넣어 구현할 수 있다.

 

최종적으로 visited배열을 통해 s->e에서 사용한 노드를 제외하고 e->s로 가는 최단 거리를 구하여 answer에 더해주면 끝

 

코드1(1번 방법)

import java.util.*

var answer=0
fun bfs(way : Int,firstdis : Int, graph : Array<ArrayList<Int>>,n : Int ,s : Int, e : Int, visited : BooleanArray) : BooleanArray{
    var firstDis =firstdis
    val q : Queue<Jogging> = LinkedList<Jogging>()
    q.add(Jogging(s,0,s.toString()))
    var firstLoad=""
    while(q.isNotEmpty()){
        var (cur , dis, load) = q.poll()
        visited[cur]=true

        //s->e일 때
        if(way==0){
            if (cur == e) {

                if (firstDis == 987654321) {
                    firstDis = dis
                    answer += dis
                   firstLoad=load
                } else if(firstDis==dis){
                    if (dis == firstDis) {
                        val tk1 = StringTokenizer(firstLoad)
                        val tk2 = StringTokenizer(load)
                        while(tk1.hasMoreTokens()){
                            if(tk1.nextToken()>tk2.nextToken()){
                                firstLoad=load
                            }
                        }
                    }
                }
                continue
            }
        }
        //e->s일 때
        else{
            if(cur ==e){
                answer+=dis
                return BooleanArray(1)
            }
        }
        for(i in graph[cur].indices){
            var next = graph[cur][i]
            if(visited[next])continue
            q.add(Jogging(next,dis+1,load+" "+next.toString()))
        }
    }
    var arr = BooleanArray(n+1)
    val tk = StringTokenizer(firstLoad)
    while(tk.hasMoreTokens()){
        val num =Integer.parseInt(tk.nextToken())
        if(num!=s){
            arr[num]=true
        }
    }
    return arr
}

 fun main() = with(System.out.bufferedWriter()){
     val br = System.`in`.bufferedReader()
     var tk = StringTokenizer(br.readLine())
     val (n,m) = List(2){ Integer.parseInt(tk.nextToken()) }
     val graph = Array<ArrayList<Int>>(n+1){ArrayList<Int>()}
     for(i in 0 until m){
         tk = StringTokenizer(br.readLine())
         val (from, to) = List(2){Integer.parseInt(tk.nextToken())}
         graph[from].add(to)
         graph[to].add(from)
     }
     tk = StringTokenizer(br.readLine())
     val (s,e) = List(2){Integer.parseInt(tk.nextToken())}
     //첫 번째 bfs에서s-e경로 찾고 지나온 경로들 visied에 true로 저장
     var visited  = bfs(0,987654321,graph,n,s,e,BooleanArray(n+1))
     //구한 visited가지고 다시 e-s경로 찾기
     bfs(1,987654321,graph,n,e,s,visited)
     write("$answer")
     close()
 }
data class Jogging(var node : Int, var dis : Int, var str : String)

코드2(2번 방법)

import java.util.*
var ans=0
fun bfs(way : Int, graph : Array<ArrayList<Int>>,n : Int ,s : Int, e : Int, visited : BooleanArray) : BooleanArray{
    val q : Queue<Jogging> = LinkedList<Jogging>()
    q.add(Jogging(s,0,s.toString()))
    var firstLoad=""
    while(q.isNotEmpty()){
        var (cur , dis, load) = q.poll()
        visited[cur]=true

        //s->e일 때
        if(way==0){
            if (cur == e) {
                firstLoad = load
                ans+=dis
                break
            }

        }
        //e->s일 때
        else{
            if(cur ==e){
                ans+=dis
                return BooleanArray(1)
            }
        }
        for(i in graph[cur].indices){
            var next = graph[cur][i]
            if(visited[next])continue
            q.add(Jogging(next,dis+1,load+" "+next.toString()))
        }
    }
    var arr = BooleanArray(n+1)
    val tk = StringTokenizer(firstLoad)
    tk.nextToken()
    while(tk.hasMoreTokens()){
        arr[Integer.parseInt(tk.nextToken())]=true
    }
    return arr
}

fun main() = with(System.out.bufferedWriter()){
    val br = System.`in`.bufferedReader()
    var tk = StringTokenizer(br.readLine())
    val (n,m) = List(2){ Integer.parseInt(tk.nextToken()) }
    val graph = Array<ArrayList<Int>>(n+1){ArrayList<Int>()}
    for(i in 0 until m){
        tk = StringTokenizer(br.readLine())
        val (from, to) = List(2){Integer.parseInt(tk.nextToken())}
        graph[from].add(to)
        graph[to].add(from)
    }
    for(i in 1 .. n){
        graph[i].sort()
    }
    tk = StringTokenizer(br.readLine())
    val (s,e) = List(2){Integer.parseInt(tk.nextToken())}
    //첫 번째 bfs에서s-e경로 찾고 지나온 경로들 visied에 true로 저장
    var visited  = bfs(0,graph,n,s,e,BooleanArray(n+1))
    //구한 visited가지고 다시 e-s경로 찾기
    bfs(1,graph,n,e,s,visited)
    write("$ans")
    close()
}
data class Jogging(var node : Int, var dis : Int, var str : String)