프로그래머스 - 49189 가장 먼 노드

03 Jul 2022

Reading time ~1 minute

문제

49189 가장 먼 노드

풀이

너비 우선 탐색(bfs)을 한다.
시작 노드를 거리를 0으로 설정하고 큐에 넣고, 탐색을 시작한다.
큐에서 노드를 꺼낸다.
이미 방문한 노드라면 처음으로 돌아간다.
연결된 노드들을 거리를 현재 노드의 거리 + 1로 설정하고 큐에 넣는다.
큐가 비면 탐색을 종료하고 마지막으로 탐색한 노드들과 같은 거리의 노드들의 수를 출력한다.

답

kotlin code

class Solution {
    fun solution(n: Int, edge: Array<IntArray>): Int {
        val map = (edge.map { intArrayOf(it[1], it[0]) } + edge).groupBy { it.first() }.map { Pair(it.key, it.value.map { m -> m.last() }.toSet() ) }.toMap()
        val visited = BooleanArray(n+1)
        val queue:java.util.Queue<Node> = java.util.LinkedList()
        queue.offer(Node(1, 0))

        var answer = 0
        var nowDistance = 0
        while (queue.isNotEmpty()) {
            val node = queue.poll()
            if(visited[node.num]) continue
            answer++
            if(node.distance != nowDistance)  {
                nowDistance = node.distance
                answer = 1
            }
            for(des in map[node.num] ?: setOf()) {
                queue.offer(Node(des, node.distance+1))
            }
            visited[node.num] = true
        }

        return answer
    }
}

data class Node(val num:Int, val distance:Int)