[프로그래머스][Summer/Winter Coding(~2018)][Kotlin]배달

class Solution {
    var townMap = mutableMapOf<Int,MutableList<Int>>()
    var townTime = mutableMapOf<MutableList<Int>,Int>()
    private var timeMap = mutableMapOf<Int,Int>()
    fun solution(N: Int, road: Array<IntArray>, k: Int): Int {
        var answer = 0
        var visited = BooleanArray(N+1){true}
        road.forEach{
            var tempList = mutableListOf<Int>()
            tempList.add(it[0])
            tempList.add(it[1])
            tempList.sort()
            if(townMap.containsKey(it[0])){
                var temp = townMap.get(it[0])!!
                temp.add(it[1])
                temp.sort()
                townMap.put(it[0],temp)
            }else{
                var temp = mutableListOf<Int>()
                temp.add(it[1])
                townMap.put(it[0],temp)
            }

            if(townMap.containsKey(it[1])){
                var temp = townMap.get(it[1])!!
                temp.add(it[0])
                temp.sort()
                townMap.put(it[1],temp)
            }else{
                var temp = mutableListOf<Int>()
                temp.add(it[0])
                townMap.put(it[1],temp)
            }

            if(townTime.containsKey(tempList)){
                if(townTime.get(tempList)!! > it[2]){
                    townTime.put(tempList,it[2])
                }
            } else {
                townTime.put(tempList,it[2])
            }
        }

        townTime.put(mutableListOf<Int>(0,1),0)
        val start = townMap.get(1)!!
        visited[1] = false
        for(i in 0 .. start.size-1){
            dfs(start[i],1, visited, townMap, townTime, 0)
        }

        answer = timeMap.values.toList().count{e -> e <= k} + 1
        return answer
    }

    private fun dfs(visit: Int, started: Int, visited: BooleanArray,
                    townMap: MutableMap<Int,MutableList<Int>>,
                    townTime: MutableMap<MutableList<Int>,Int>, time: Int){

        var visitedArray = visited
        visitedArray[visit] = false // 방문기록 남기기
        var visitedTime = townTime.get(mutableListOf(visit,started).sorted())!! + time // 여기까지 도착한 시간
        if(timeMap.containsKey(visit)){ // 시간 비교하여 짧은 시간 갱신
            if(timeMap.get(visit)!! > visitedTime){
                timeMap.put(visit,visitedTime)
            } else {
                return
            }
        } else {
            timeMap.put(visit,visitedTime)
        }

        val visitedList = townMap.get(visit)!!.distinct().filter{it != 1}
        for(i in 0 .. visitedList.size-1){
            visitedArray[visitedList[i]] = true
            if(visitedArray[visitedList[i]]){
                dfs(visitedList[i],visit,visitedArray,townMap,townTime,visitedTime)   
            }
        }

    }

}

 DFS공부하던 중 해당문제를 발견하여 풀어보았습니다.

아직 공부부족이라 썻다 지웠다를 몇번을 반복했는지 모르겠습니다ㅠㅜ

아직까지 대략적인 틀은 잡았지만 세부적으로 원활하게 제가 다룰 수 없는 느낌입니다.

상기코드는를 작성 후 무사히 통과 후 다른사람들의 코드를 보았는데 저는 이제 막 걸음마를 시작한 아기레벨 같다는 느낌이 들었습니다. 다른사람의 통과 코드를 한번 실행해 보았는데 실행시간부터가 매우 차이가 나는 것을 보고 충격을 좀 쎄게 받았던 것 같습니다.

추후 더욱 다양한 알고리즘 등을 공부하여 해당 문제를 깔끔하게 다시 작성 할 수 있도록 하겠습니다.

아래는 실행 결과 입니다.

테스트 1 〉	통과 (19.66ms, 63.7MB)
테스트 2 〉	통과 (17.53ms, 62.9MB)
테스트 3 〉	통과 (24.35ms, 62.6MB)
테스트 4 〉	통과 (21.69ms, 62.9MB)
테스트 5 〉	통과 (21.23ms, 63.1MB)
테스트 6 〉	통과 (31.18ms, 63.2MB)
테스트 7 〉	통과 (19.69ms, 63.8MB)
테스트 8 〉	통과 (16.68ms, 63.5MB)
테스트 9 〉	통과 (20.40ms, 63.7MB)
테스트 10 〉	통과 (18.81ms, 63.5MB)
테스트 11 〉	통과 (18.97ms, 63MB)
테스트 12 〉	통과 (19.20ms, 64.2MB)
테스트 13 〉	통과 (29.45ms, 63.7MB)
테스트 14 〉	통과 (140.97ms, 108MB)
테스트 15 〉	통과 (261.27ms, 116MB)
테스트 16 〉	통과 (25.75ms, 63.6MB)
테스트 17 〉	통과 (26.45ms, 63MB)
테스트 18 〉	통과 (75.93ms, 93.5MB)
테스트 19 〉	통과 (260.43ms, 120MB)
테스트 20 〉	통과 (59.88ms, 90.5MB)
테스트 21 〉	통과 (273.72ms, 111MB)
테스트 22 〉	통과 (83.45ms, 91.9MB)
테스트 23 〉	통과 (242.14ms, 118MB)
테스트 24 〉	통과 (206.45ms, 114MB)
테스트 25 〉	통과 (361.40ms, 199MB)
테스트 26 〉	통과 (290.54ms, 179MB)
테스트 27 〉	통과 (256.58ms, 123MB)
테스트 28 〉	통과 (251.56ms, 170MB)
테스트 29 〉	통과 (297.50ms, 185MB)
테스트 30 〉	통과 (133.86ms, 103MB)
테스트 31 〉	통과 (18.95ms, 64.4MB)
테스트 32 〉	통과 (39.01ms, 73MB)