[프로그래머스][Kotlin]가장 먼 노드

해당 문제는 BFS 사용하여 작성 할 수 있으며, 작성 시 주의 할 점은 출발 점은 항상 1번 노드라는 점과

BFS를 공부하신 분들은 알겠지만 방문처리 등등 은 deque에 넣을 때 동시에 해야 된다는 점입니다.

 

하기는 제가 작성한 코드와 실행 결과 입니다.

 

import java.util.ArrayDeque

class Solution {
    fun solution(n: Int, edge: Array<IntArray>): Int {
        var len = IntArray(n+1){0} // 거리를 저장할 배열
        var node = Array(n+1,{ArrayList<Int>()})
        var visit = BooleanArray(n+1){true}
        edge.forEach {
            node[it[0]].add(it[1])
            node[it[1]].add(it[0])
        }

        var dq = ArrayDeque<Int>()
        dq.add(1)
        len[1] = 0

        var max = 0
        while(!dq.isEmpty()){
            var now = dq.pollFirst()
            visit[now] = false

            for(i in 0 .. node[now].size-1){
                if(visit[node[now][i]]){
                    visit[node[now][i]] = false
                    dq.addLast(node[now][i])
                    len[node[now][i]] = len[now]+1
                    max = len[now]+1
                }
            }

        }
        return len.count{e -> e == max}
    }
}

테스트 1 〉	통과 (0.07ms, 62.3MB)
테스트 2 〉	통과 (0.11ms, 61.7MB)
테스트 3 〉	통과 (0.15ms, 61MB)
테스트 4 〉	통과 (0.86ms, 59.7MB)
테스트 5 〉	통과 (2.68ms, 61.8MB)
테스트 6 〉	통과 (5.60ms, 65.4MB)
테스트 7 〉	통과 (18.65ms, 76.1MB)
테스트 8 〉	통과 (36.53ms, 84.7MB)
테스트 9 〉	통과 (35.25ms, 83MB)