[프로그래머스] Lv 3. 네트워크(Kotlin)

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

 

문제

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

 

풀이

서로 연결되어 있는 집단의 개수를 구할 때는 DFS(깊이우선탐색)을 사용할 수 있습니다.

 

코드

class Solution {
    fun solution(n: Int, computers: Array<IntArray>): Int {
        var answer = 0
        
        val visited = BooleanArray(n, { false })
        for (start in 0 until n) {
            if (visited[start].not()) {
                answer += 1
                dfs(start,visited,computers,n)
            }
        }
        return answer
    }
    
    fun dfs(start: Int, visited: BooleanArray, computers: Array<IntArray>, n: Int) {
        visited[start] = true
        
        for (end in 0 until n) {
            if (computers[start][end] == 1 && visited[end].not()) {
                dfs(end, visited, computers,n)
            }
        }
    }
}