[구름톤 챌린지 19일차] [Kotlin] 대체 경로

https://level.goorm.io/l/challenge/goormthon-challenge?utm_source=notion&utm_medium=cta&utm_content=open&_gl=1*1lv0w8b*_gcl_au*MTA2NTY4MTU0My4xNjkyMDE0OTc4 

구름LEVEL

 

 

구름톤 알고리즘 챌린지 19일차 : 대체 경로

구름톤 알고리즘 챌린지 19일차 문제인 대체 경로 입니다.

1일부터 n일까지, i일에는 i번째 도시가 공사를 한다고 하였을 때,

해당 도시가 공시중일 때 시작 도시에서 도착 도시로 가는 최단 경로를 찾는 문제였습니다.

 

단순 최단 경로라면 BFS를 사용한 최단경로 찾기 기법을 사용하면 되겠지만

해당 문제는 하루에 한 도시씩 봉쇄된다는 조건이 있습니다.

 

어떻게 구할 수 있을까 고민을 하다가,

그냥 브루트포스적 방법을 섞어, 각 도시가 봉쇄되었을 경우마다 BFS를 돌려볼까? 하는 생각으로,

n번의 BFS를 진행하였습니다.

 

 

 

 

전체 소스코드

import java.util.LinkedList
import java.util.Queue

fun main() = with(System.`in`.bufferedReader()) {
    val (n, m, start, end) = readLine().split(" ").map(String::toInt)

    val connect = Array(n + 1) { ArrayList<Int>() }
    val minDistanceWhenCityBlocked = IntArray(n + 1) { Int.MAX_VALUE }

    repeat(m) {
        val (a, b) = readLine().split(" ").map(String::toInt)
        connect[a].add(b)
        connect[b].add(a)
    }

    val visited = IntArray(n + 1) { 0 }

    // 각각의 도시가 봉쇄되었을 경우마다 BFS 수행
    for (blockedCity in 1..n) {
        visited.fill(0)
        visited[start] = 1

        val q = LinkedList<Int>() as Queue<Int>
        q.offer(start)

        bfs@ while (q.isNotEmpty()) {
            val currentCity = q.poll()

            for (i in 0 until connect[currentCity].size) {
                val nextCity = connect[currentCity][i]

                if (visited[nextCity] != 0 || nextCity == blockedCity) continue

                visited[nextCity] = visited[currentCity] + 1
                q.offer(nextCity)

                if(nextCity == end) {
                    minDistanceWhenCityBlocked[blockedCity] = visited[nextCity]
                    break@bfs
                }
            }
        }
    }

    val sb = StringBuilder()
    minDistanceWhenCityBlocked[start] = -1
    minDistanceWhenCityBlocked[end] = -1
    for (i in 1..n) {
        if (minDistanceWhenCityBlocked[i] == Int.MAX_VALUE) sb.append(-1).append("\n")
        else sb.append(minDistanceWhenCityBlocked[i]).append("\n")
    }
    print(sb)
}

 

 

 

후기

처음에 단순하게 BFS를 n번 돌려 구현하였을 때 시간초과가 나서,

역시 너무 단순하게 생각했나... 하는 마음에 다른 방법을 고민해봤으나,

 

인접 행렬을 인접 리스트로 고쳤더니 풀렸네요.

다른 알고리즘을 생각하느냐 꽤 고민했는데 다소 허무했습니다... ㅠ

 

그래프 탐색 시 인접 리스트의 시간복잡도는 O(V+E), 인접행렬의 시간복잡도는 O(V^2) 임을 기억하며,

주어진 상황에 적합한 인접 노드 표현 방법을 생각해봅시다!