프로그래머스 Level 3 가장 먼 노드 코틀린 Kotlin

https://programmers.co.kr/learn/courses/30/lessons/49189

코딩테스트 연습 - 가장 먼 노드

 

안녕하세요!

오랜만입니다 ㅎㅎ...ㅠㅠ

 

오늘은 프로그래머스 Level 3 가장 먼 노드 문제를 풀어봤습니다

오랜만에 자바가 아닌 코틀린으로 문제를 풀어봤습니다!!

 

• 가장 먼 노드

문제 설명

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

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

제한사항

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

입출력 예nvertexreturn

6

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

3

입출력 예 설명

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

이 문제를 좀 더 쉽게 이해하려면 먼저 위에 이미지를 옆으로 회전시켜보면

밑에 이미지 처럼 됩니다

이렇게 되면 1번 노드는 level 1. , 2,3 노드는 level 2

4,5,6노드는 level 3이 됩니다

 

즉 1번 노드에서 가장 먼 노드는 level 이 큰 노드가 해당됩니다 ! 

그리고 1번 노드를 제외한 나머지 노드의 레벨은 상위 노드의 level + 1 이 자신의 Level이 됩니다 

이것을 활용하면 문제를 쉽게 풀 수 있습니다!!

아 그리고 이 문제는 배열이 아닌 리스트 형식으로 문제를 풀어야합니다!

배열로 풀게 되면 마지막 8, 9번 문제는 메모리 초과가 뜹니다 ㅎㅎ

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

class Solution {

     var array : Array<ArrayList<Int>> = arrayOf()
    var visited : BooleanArray = booleanArrayOf();
    var dist  : IntArray = intArrayOf()
    var size =0

    fun solution(n: Int, edge: Array<IntArray>): Int {
        var answer = 0
        size = n
        array = Array(n+1){ ArrayList() }
        dist = IntArray(n+1){0}
        visited = BooleanArray(n+1)
        for(i in edge.indices){
            array[edge[i][0]].add(edge[i][1])
            array[edge[i][1]].add(edge[i][0])
        }
        bfs()
        dist.sortDescending()

        var max = dist[0]

        for(i in dist.indices){
            if(max==dist[i]){
                answer++
            }else{
                break
            }
        }


        return answer
    }

    fun bfs() : Unit {
        var list : LinkedList<Int> = LinkedList()
        visited[1] = true
        list.add(1)
        dist[1] = 1
        while (list.isNotEmpty()){
            val now = list.poll()
            for(i in array[now].indices){
                var num = array[now][i]
                if(!visited[num]){
                    visited[num]=true
                    dist[num] = dist[now]+1
                    list.add(num)
                }
            }

        }

    }


}

fun main(){
    var solution = Solution();

    println(
        solution.solution(6, arrayOf(intArrayOf(3,6),
            intArrayOf(4,3),
            intArrayOf(3,2),
            intArrayOf(1,3),
            intArrayOf(1,2),
            intArrayOf(2,4),
            intArrayOf(5,2),
        ))
    )


}