Programmers :: DFS(깊이 우선 탐색법) 네트워크 레벨 3

풀이

import java.util.*

class Solution {
    fun solution(n: Int, computers: Array<IntArray>): Int {
        val graph = Graph(n, computers)
        graph.buildEdge(
            graph.computersToRelationList()
        )

        return graph.getNetworkSize()
    }
}

class Graph(n: Int, computers: Array<IntArray>) {

    val N: Int = n
    val adj = Array<LinkedList<Int>>(N) { LinkedList() }

    val computers = computers

    fun buildEdge(relationList: List<Map<Int, Int>>) {
        relationList.forEach { relation ->
            this.adj
                .get(relation.keys.first())
                .add(relation.values.first())
        }
    }

    fun computersToRelationList(): List<Map<Int, Int>> {
        return this.computers.mapIndexed { index, computer ->
            computer
                .mapIndexed { flatIndex, flatComputer ->
                    if (flatComputer != 0) {
                        if (index != flatIndex) {
                            mapOf(pair = Pair(index, flatIndex))
                        } else {
                            null
                        }
                    } else {
                        null
                    }
                }
                .filterNotNull()
        }.flatten()
    }

    fun DFS(v: Int): List<Boolean> {
        val visited = Array<Boolean>(N) { false }

        DFSUtil(v, visited)

        return visited.toList()
    } 

    fun DFSUtil(v: Int, visited: Array<Boolean>) {
        visited.set(v, true)

        val iter = this.adj.get(v).iterator()

        while (iter.hasNext()) {
            val next = iter.next()

            if (visited.get(next) == false) {
                DFSUtil(next, visited)
            }
        }
    }

    fun getNetworkSize(): Int{

        val networkList = mutableListOf<List<Boolean>>()

        for(i in 0 until N){
            networkList.add(this.DFS(i))
        }

        return networkList.distinct().size

    }
}

---

출처

코딩테스트 연습 - 네트워크

 

---

참고

[알고리즘] 깊이 우선 탐색(DFS)이란 - Heee's Development Blog