릿코드 815. Bus Routes 코틀린

각 정류장마다 갈수있는 길(버스)이 있는 그래프로 잡고 소스를 시작점으로 bfs를 돌렸음->메모리초과

import java.util.*
import kotlin.math.min
import kotlin.reflect.typeOf

class Solution {
    fun numBusesToDestination(routes: Array<IntArray>, source: Int, target: Int): Int {
        val routeList=routes.map{it.toList()}.toList()
        val maxStation:Int=routeList.flatten().max()
        val INF=1000000000

        val costList= MutableList(maxStation+1){INF}

        val busRouteList= MutableList(maxStation+1){ mutableSetOf<Int>() }

        for (bus in routeList){
            for (route in bus){
                busRouteList[route].addAll(bus)
                busRouteList[route].remove(route)

            }

        }

        costList[source]=0
        val queue=PriorityQueue<Int>()
        queue.add(source)
        while (queue.isNotEmpty()){
            val curLocation=queue.poll()
            for(i in busRouteList[curLocation]){
                if (costList[i]>costList[curLocation]+1){
                    costList[i]= costList[curLocation]+1
                    queue.add(i)
                }
            }
        }


        if (costList[target]==INF){
            return -1
        }
        return  costList[target]
    }
}

목적지를 시작점으로 잡고 시작점나오면 바로 리턴하게하고 우선순위큐를 큐로 변경->메모리 or 시간초과

import java.util.*
import kotlin.math.min
import kotlin.reflect.typeOf

class Solution {
    fun numBusesToDestination(routes: Array<IntArray>, source: Int, target: Int): Int {
        val routeList=routes.map{it.toList()}.toList()
        val maxStation:Int=routeList.flatten().max()
        val INF=1000000000

        val costList= MutableList(maxStation+1){INF}

        val busRouteList= MutableList(maxStation+1){ mutableSetOf<Int>() }

        if (target==source) return 0

        for (bus in routeList){
            for (route in bus){
                busRouteList[route].addAll(bus)
                busRouteList[route].remove(route)

            }

        }
        costList[target]=0
        val queue:Queue<Int> =LinkedList()
        queue.add(target)

        while (queue.isNotEmpty()){
            val curLocation=queue.poll()
            for(i in busRouteList[curLocation]){

                if (costList[i]>costList[curLocation]+1){
                    costList[i]= costList[curLocation]+1
                    queue.add(i)
                    
                    if (i==source){
                        return costList[i]
                    }
                }
            }
        }



        return -1


    }
}

 

 

정답

class Solution {

    data class Route(val reach: MutableSet<Int> = mutableSetOf(), val index: Int)

    data class BfsElement(val stop: Int, val height: Int)

    fun numBusesToDestination(rawRoutes: Array<IntArray>, source: Int, target: Int): Int {
        val routes = mutableListOf<Route>()
        val positionToRoute = mutableMapOf<Int, MutableList<Int>>()
        for((i, r) in rawRoutes.withIndex()) {
            val rte = Route(index = i)
            r.forEach {
                rte.reach.add(it)
                val routesForPos = positionToRoute[it] ?: mutableListOf()
                routesForPos.add(i)
                positionToRoute[it] = routesForPos
            }
            routes.add(rte)
        }
        val q = LinkedList<BfsElement>()
        q.offer(BfsElement(source, 0))
        val qIncl = mutableSetOf<Int>()
        qIncl.add(source)
        val visited = mutableSetOf<Int>()
        while(!q.isEmpty()) {
            val next = q.poll()!!
            if(visited.contains(next.stop)) {
                continue
            }
            //println("Visiting >> ${next}")
            visited.add(next.stop)
            if(next.stop == target) {
                return next.height
            }
            for(r in positionToRoute[next.stop] ?: mutableListOf()) {
                for(stop in routes[r].reach) {
                    if(!visited.contains(stop) && !qIncl.contains(stop)) {
                        q.offer(BfsElement(stop, next.height+1))
                    }
                }
                routes[r].reach.clear()
            }
        }
        return -1
    }
}