[프로그래머스] 네트워크

사용 언어: Kotlin

 

문제

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

프로그래머스

2대 이상의 컴퓨터가 직/간접적으로 연결된 것을 같은 하나의 네트워크라고 봤을 때, 컴퓨터 개수 n, 컴퓨터 간 연결 정보 computers가 주어지고, 네트워크의 개수를 return한다.

제한사항

 1 <= n <= 200

각 컴퓨터를 0~n-1 정수로 표현.

0번 컴퓨터와 1번 컴퓨터의 연결을 computers[0][1]로 표현

풀이

기본적인 DFS/BFS 문제이다. 특정 네트워크를 탐색할 때, 포함되지 않는 컴퓨터는 visit을 순회하며 재탐색한다.

코드

fun solution(n: Int, computers: Array<IntArray>): Int {
    val visited = BooleanArray(n) { false }
    var result = 0
    for(i in 0 until n) {
        if (!visited[i]) {
            dfs(computers, visited, i)
            result++
        }
    }
    return result
}

fun dfs(computers: Array<IntArray>, visited: BooleanArray, computerIdx: Int) {
    if(visited[computerIdx]) return
    visited[computerIdx] = true
    computers[computerIdx].forEachIndexed { idx, it ->
        if(it==1) dfs(computers, visited, idx)
    }
}