[프로그래머스][Kotlin] 부대복귀

해당 문제는 BFS를 이용하여 풀 수 있습니다.

해당 문제를 작성하면서 처음에 작성하였었던 코드가 시간 초과가 나왔었습니다.

원인을 처음에는 못찾았었지만 문제 설명, 제한사항, 입출력 예등을 보다 보니 제가 처음에 작성한 코드가 시간 초과가 날 수밖에 없는 이유를 찾았었습니다. 제가 bfs를 sources의 size 만큼 돌리면서 길이를 찾는 코드를 작성 했었기 때문입니다.

문제의 설명을 자세히 보지 않아 destination 으로부터의 거리를 구하면 되는 문제를 각 출발 지점부터의 destination 거리를 쓸데 없이 bfs를 더욱 반복하여 시간 초과가 나왔던 것입니다.

앞으로는 문제를 대충 읽어 작성 및 디버깅 시간이 늘어나는 실수를 하지 않도록 해야겠다는 생각을 하게 되었습니다.하기는 제가 작성한 코드와 실행 결과 입니다.

import java.util.*
import kotlin.collections.ArrayList

class Solution {
    fun solution(n: Int, roads: Array<IntArray>, sources: IntArray, destination: Int): IntArray {
        var answer = intArrayOf()
        var roadList = ArrayList<ArrayList<Int>>()

        repeat(n+1){
            roadList.add(ArrayList())
        }

        for(i in 0 .. roads.size-1){
            roadList[roads[i][0]].add(roads[i][1])
            roadList[roads[i][1]].add(roads[i][0])
        }

        var lenCount =  IntArray(n+1){-1}
        var dq = ArrayDeque<Int>()
        dq.addFirst(destination)
        lenCount[destination] = 0

        while(!dq.isEmpty()){
            val now = dq.pollFirst()
            for(nextRoad in roadList[now]){
                if(lenCount[nextRoad] == -1){
                    dq.addLast(nextRoad)
                    lenCount[nextRoad] = lenCount[now]+1
                }
            }
        }

        sources.forEach {
            answer += lenCount[it]
        }

        return answer
    }
}

테스트 1 〉	통과 (10.05ms, 63.7MB)
테스트 2 〉	통과 (9.62ms, 63MB)
테스트 3 〉	통과 (13.30ms, 65.2MB)
테스트 4 〉	통과 (10.47ms, 63.5MB)
테스트 5 〉	통과 (9.46ms, 63.3MB)
테스트 6 〉	통과 (30.50ms, 84.6MB)
테스트 7 〉	통과 (37.93ms, 80.8MB)
테스트 8 〉	통과 (35.02ms, 86MB)
테스트 9 〉	통과 (31.12ms, 76.1MB)
테스트 10 〉	통과 (30.82ms, 76.3MB)
테스트 11 〉	통과 (149.47ms, 161MB)
테스트 12 〉	통과 (243.31ms, 158MB)
테스트 13 〉	통과 (192.23ms, 159MB)
테스트 14 〉	통과 (192.56ms, 160MB)
테스트 15 〉	통과 (137.54ms, 162MB)
테스트 16 〉	통과 (47.50ms, 98.9MB)