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

Level3 - 가장 먼 노드

프로그래머스

문제

문제 설명

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

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

제한사항

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

입출력 예

n vertex return

6

[[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]

3

입출력 예 설명

예제의 그래프를 표현하면 아래 그림과 같고, 1번 노드에서 가장 멀리 떨어진 노드는 4,5,6번 노드입니다.

풀이

나의 최종 풀이

풀이 접근 과정

결국은 각 지점별 ‘최단경로’들을 구해 그 경로들 중 가장 먼 노드를 찾으면 될 것이라 판단했습니다. 그때 바로 생각난 최단경로를 구하는 법은 다익스트라 알고리즘이었습니다. 그래서 다익스트라 알고리즘으로 문제를 풀었습니다.

최종 소스코드

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

class Solution {
    private lateinit var graph: Array<ArrayList<Int>>
    private lateinit var distance: IntArray
    private var max = 0

    fun solution(n: Int, edge: Array<IntArray>): Int {
        graph = Array(n+1) { arrayListOf() }
        distance = IntArray(n+1) { Int.MAX_VALUE }

        edge.forEach {
            graph[it[0]].add(it[1])
            graph[it[1]].add(it[0])
        }

        dijkstra(1)

        return searchMaxCount()
    }

    fun dijkstra(start: Int) {
        val q = PriorityQueue<Node>()

        q.add(Node(start, 0))
        distance[start] = 0

        while (q.isNotEmpty()) {
            val (now, dist) = q.poll()
            if (distance[now] < dist) continue

            for (i in graph[now]) {
                val cost = dist + 1

                if (cost < distance[i]) {
                    distance[i] = cost
                    q.add(Node(i, cost))
                }
            }
        }
    }

    private fun searchMaxCount(): Int {
        var count = 0
        distance.forEach {
            if (it == Int.MAX_VALUE) return@forEach
            if (it > max) {
                count = 1
                max = it
            } else if (it == max) {
                count++
            }
        }
        return count
    }

    data class Node(val index : Int, val value : Int) : Comparable<Node> {
        override fun compareTo(other: Node): Int = value - other.value
    }
}

이 코드는 무방향 그래프와 다익스트라 알고리즘을 활용하여, 1번 노드로부터 최단 경로로 도달 가능한 노드들 중에서, 최단 경로의 길이가 가장 큰 노드의 개수를 반환합니다.

먼저, 주어진 무방향 그래프를 인접 리스트로 표현하기 위해 graph 배열을 생성합니다. 그리고 각 노드의 최단 경로 길이를 저장하기 위한 distance 배열을 생성하고, 최단 경로의 길이가 가장 긴 노드의 길이를 저장하기 위한 max 변수를 초기화합니다.

그 다음, edge 배열에 저장된 간선 정보를 이용하여 인접 리스트 **graph**를 구성합니다. 구성된 인접 리스트를 바탕으로 다익스트라 알고리즘을 실행하여, 1번 노드로부터 각 노드까지의 최단 경로 길이를 계산하고, distance 배열에 저장합니다.

최단 경로 길이가 가장 긴 노드의 개수를 구하기 위해서는, distance 배열에서 최댓값을 찾아서 그 값과 일치하는 원소의 개수를 세어야 합니다. 이를 위해 searchMaxCount 함수를 만들고, distance 배열을 순회하면서 최댓값을 찾고, 최댓값과 일치하는 원소를 찾으면 개수를 증가시킵니다.

마지막으로, searchMaxCount 함수에서 계산된 개수를 반환합니다.

다른 사람의 풀이

import java.util.*

class Solution {
    fun solution(n: Int, edge: Array<IntArray>): Int {
        val graph = Array(n + 1) { mutableListOf<Int>() }
        val distances = IntArray(n + 1) { Int.MAX_VALUE }
        val visited = BooleanArray(n + 1)

        for (e in edge) {
            graph[e[0]].add(e[1])
            graph[e[1]].add(e[0])
        }

        val q = LinkedList<Int>()
        q.offer(1)
        visited[1] = true
        distances[1] = 0

        while (q.isNotEmpty()) {
            val node = q.poll()

            for (next in graph[node]) {
                if (!visited[next]) {
                    visited[next] = true
                    distances[next] = distances[node] + 1
                    q.offer(next)
                }
            }
        }

        val maxDistance = distances.maxOrNull()!!
        return distances.count { it == maxDistance }
    }
}

이 코드는 너비 우선 탐색(BFS) 알고리즘을 사용하여 푼 것입니다. BFS는 시작 노드에서부터 거리가 가까운 노드부터 탐색을 진행하며, 이를 이용하여 최단 거리를 구하는데 주로 사용됩니다. 이 문제에서도 각 노드까지의 최단 거리를 구해야 하기 때문에 BFS를 사용하는 것이 적절합니다.

주어진 무방향 그래프를 인접 리스트로 구현하기 위해 graph 배열을 생성합니다. 그리고 각 노드까지의 최단 거리를 저장하기 위한 distances 배열을 생성하고, 방문 여부를 저장하기 위한 visited 배열을 생성합니다.

그 다음, edge 배열에 저장된 간선 정보를 이용하여 인접 리스트 **graph**를 구성합니다. 그리고 BFS 알고리즘을 실행하여, 1번 노드로부터 각 노드까지의 최단 거리를 계산하고, distances 배열에 저장합니다.

최단 거리가 가장 먼 노드의 개수를 구하기 위해서는, distances 배열에서 최댓값을 찾아서 그 값과 일치하는 원소의 개수를 세어야 합니다. 이를 위해 maxDistance 변수를 이용하여 최댓값을 찾고, count 함수를 이용하여 최댓값과 일치하는 원소의 개수를 구합니다.

마지막으로, 구한 최댓값의 개수를 반환합니다.