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

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

프로그래머스

📌 문제

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

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

 

 

📌 제한 사항

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

📌 풀이

 

 0. 공통 사항

• 각 노드가 1노드에서부터 얼마나의 최단 거리를 갖는 지를 구하는 것이 핵심이다.
• 연결 상황을 2차원 배열로 표시했지만 메모리 초과를 경험함
  • 2차원 배열 -> 배열 안에 리스트로 수정함
  • 인접한 노드들로만 리스트를 구성하여 포문을 단축시키고 메모리를 줄일 수 있음
• 출발점 (1노드)에서부터의 거리를 담는 1차원 배열을 선언
  • 탐색시 방문한 노드에 대해 체크할 수 있는 리스트의 기능 까지 수행함

 

 1. DFS 를 통한 풀이

 

• DFS 로 거리를 구하고 계속 탐색해나가면서 최단 거리로 갱신해 나가는 로직
• 그래프가 커짐에 따라 최종적으로 유효하지 않은 탐색이 시간 초과를 유발함

  private fun dfs(startPoint: Int, layer: Int) {
        visited[startPoint] = kotlin.math.min(layer, visited[startPoint])
        map[startPoint].forEach {
            if (visited[it] > layer) {
                dfs(it, layer + 1)
            }
        }
    }

 

 2. BFS 를 통한 풀이

• 최초에 Layer 라는 개념을 만들어 queue 에 Pair 로 (point, layer) 로 저장
  • Bfs 의 특징을 통해 layer 개념을 없앰
  • Pair 로 인해 많은 리소스 낭비가 이루어짐을 경험 (시간 초과)
• bfs 검사 후 최대거리 값을 찾고 그에 해당하는 노드들의 개수를 셈
  • bfs 검사 도중 최대 거리를 미리 찾아 놓는 것으로 시간 단축
    • 합사건이더라도 최대한 포문은 줄이자!
• bfs 에서 자주하는 실수로 Poll 할때 방문처리가 아닌 넣는 for 문 안에서 방문처리를 해야한다.
  • 시간을 아낄 수 있고 때에 따라서는 정답에도 영향을 줄 수 있다.
  • 본 문제에서는 방문처리가 아닌 거리 할당

private fun bfs(startPoint: Int) {
        val queue = LinkedList<Int>()

        queue.add((startPoint))
        while (queue.isNotEmpty()) {
            val newPoint = queue.poll()
            maxLayer = max(visited[newPoint], maxLayer)
            map[newPoint].forEach {
                if (visited[it] > visited[newPoint] + 1) {
                    queue.add(it)
                    visited[it] = visited[newPoint] + 1
                }
            }
        }
    }

 

📍 전체풀이

 

import java.lang.Math.max
import java.util.LinkedList

class Solution {
    private lateinit var map: Array<MutableList<Int>>
    private lateinit var visited: Array<Int>
    var answer = 0
    var maxLayer = 0
    fun solution(n: Int, edge: Array<IntArray>): Int {

        visited = Array(n + 1) { n }
        visited[0] = 0
        visited[1] = 0

        map = Array(n + 1) { mutableListOf() }
        edge.forEach {
            map[it[0]].add(it[1])
            map[it[1]].add(it[0])
        }
        bfs(1)
        return visited.count { it == maxLayer }
    }

    private fun bfs(startPoint: Int) {
        val queue = LinkedList<Int>()

        queue.add((startPoint))
        while (queue.isNotEmpty()) {
            val newPoint = queue.poll()
            //layer = newPoint.second
            maxLayer = max(visited[newPoint], maxLayer)
            map[newPoint].forEach {
                if (visited[it] > visited[newPoint] + 1) {
                    queue.add(it)
                    visited[it] = visited[newPoint] + 1
                }
            }
        }
    }
}