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

문제 설명

n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.

노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.

 

제한사항

• 노드의 개수 n은 2 이상 20,000 이하입니다.
• 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다.
• vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.

---

풀이

처음엔 dfs를 적용해서 풀었다.

단방향이 아닌 양방향이기 때문에 주어지는 값은 접근하기 어려울 것 같아 map으로 먼저 처리하고 시작했다.

class Solution {
    fun solution(n: Int, edge: Array<IntArray>): Int {
        var answer = 0
        val distance = IntArray(n + 1) { 50_000 }
        val visit: BooleanArray = BooleanArray(n+1) { false }

        val graph: MutableMap<Int, MutableSet<Int>> = mutableMapOf()
        edge.forEach {
            graph.putIfAbsent(it[0], mutableSetOf())
            graph.putIfAbsent(it[1], mutableSetOf())
            graph[it[0]]?.add(it[1])
            graph[it[1]]?.add(it[0])
        }
        fun dfs(depth: Int, current: Int) {
            if (depth < distance[current]){
                distance[current] = depth
            }
                graph.forEach {
                    if (it.key == current) {
                        it.value.forEach {
                            if(!visit[it]){
                                visit[it] = true
                                dfs(depth + 1, it)
                                visit[it] = false
                            }
                        }
                    }
                }
        }
        dfs(0, 1)
        val max = distance.filter { it!=50000 }.maxOrNull() ?: 0
        answer = distance.filter {it == max}.size
        return answer
    }
}

하지만 시간초과...

아무래도 bfs가 더 효율적이라 생각이 들긴 했긴 했는데.. 결국 bfs 안쓰고는 시간초과가 해결 안될거같아서 bfs 공부를 먼저 한 후에 적용시켜봤다.

class Solution {
    fun solution(n: Int, edge: Array<IntArray>): Int {
        var answer = 0
        val que = ArrayDeque<Int>() //인접 노드 저장
        val visit = BooleanArray(n + 1) { false } //방문 여부
        val edges: MutableMap<Int, MutableSet<Int>> = mutableMapOf()
        edge.forEach {
            edges.getOrPut(it[0]) { mutableSetOf() }.add(it[1])
            edges.getOrPut(it[1]) { mutableSetOf() }.add(it[0])
        }
        //초깃값 설정
        que.addLast(1)
        visit[1] = true
        var depth = 0
        val depthOfNodes: MutableMap<Int, MutableSet<Int>> = mutableMapOf()// key = depth, value = nodes
        depthOfNodes[depth] = mutableSetOf(1)

        while (que.isNotEmpty()) {
            depth++
            val size = que.size

            for (i in 0 until size) {
                val value = que.removeFirst()
                edges[value]?.forEach {
                    if (!visit[it]) {
                        que.addLast(it)
                        visit[it] = true
                        depthOfNodes.getOrPut(depth) { mutableSetOf() }.add(it)
                    }
                }
            }
        }
        val maxDepth = depthOfNodes.maxOf { it.key }
        answer = depthOfNodes[maxDepth]!!.size
        return answer
    }
}

풀렸다링

 

문제 링크