가장 먼 노드

🔒 문제

💭 생각의 흐름

모든 그래프를 순회해야 함 -> DFS? BFS?

DFS vs BFS

• DFS 에서의 가장 먼 노드 판별법
  재귀호출 마다 부모노드를 킵하며 방문 가능한 인접노드가 전혀 존재하지 않는 노드 (Leaf node)
  ⚠️ 사이클이 존재하는 그래프에서 반례가 있으므로 유의

• BFS 에서의 가장 먼 노드 판별법
  라운드별로 한 depth 씩 뻗어나가므로 각 depth를 keep하는 배열을 선언하고 자신을 호출한 부모노드 배열의 depth + 1
  👉 가장 depth 값이 큰 노드
  ⚠️ 사이클 유무 무관

∵ BFS의 모든 라운드에서 부모 - 자식간의 depth 차이는 1이다.
∴ 한번에 한 Depth씩 긁는 BFS가 풀이하기 더 쉽다고 판단.

인접 행렬을 인접 리스트로 전환하고
방문 여부와 depth level만을 킵할 배열을 선언한다.

🔑 풀이 (Kotlin)

import java.util.*

enum class Vertex {
    Source,
    Destination
}

class Solution {
    lateinit var adjacentList : Array<ArrayList<Int>>

    fun connectEdge(edge: Array<IntArray>) {
        // add edge for making adjacentList
        edge.forEach {
            // undirected Graph
            adjacentList[it[Vertex.Source.ordinal]].add(it[Vertex.Destination.ordinal])
            adjacentList[it[Vertex.Destination.ordinal]].add(it[Vertex.Source.ordinal])
        }
    }

    fun solution(n: Int, edge: Array<IntArray>): Int {
        val visited: BooleanArray = BooleanArray(n + 1)
        val depth: IntArray = IntArray(n + 1) { 0 }

        val queue: Queue<Int> = LinkedList<Int>()
        adjacentList = Array(n + 1) { ArrayList<Int>() }

        connectEdge(edge)

        queue.add(1)
        visited[1] = true
        
	// BFS keeping depth!
        while (queue.isNotEmpty()) {
            val sourceNode = queue.poll()

            for (adjacentVertex in adjacentList[sourceNode]) {
                if (!visited[adjacentVertex]) {
                    visited[adjacentVertex] = true
                    queue.add(adjacentVertex)
                    // keep the level of BFS
                    depth[adjacentVertex] = depth[sourceNode] + 1
                }
            }
        }
		//가장 먼 노드의 depth
        val depthMax = depth.max()
        // 가장 먼 노드 depth 와 길이가 같은 노드 갯수 == 가장 먼 노드 갯수
        return depth.count { it == depthMax }
    }
}

결과

Reference

BFS에서 depth를 keep하는 아이디어