네트워크 - Kotlin (BFS)

프로그래머스

문제 설명

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.

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

 

 

나의 풀이

이 문제는 BFS를 이용해서 해결하였다. 한 노드에서 시작해 가능한 곳까지 진행해보고 만약에 막힌다면 다른 노드부터 다시 네트워크를 시작하게 코드를 작성했다.

 

import java.util.*
import kotlin.math.*

class Solution {
    lateinit var visited : BooleanArray
    lateinit var graph : Array<MutableList<Int>>
    
    fun solution(n: Int, computers: Array<IntArray>): Int {
        var answer = 0
        visited = BooleanArray(n + 1)
        graph = Array(n + 1) { mutableListOf<Int>() }
        
        for (i in 0 until n) {
            for (j in 0 until n) {
                if (i != j && computers[i][j] == 1)
                    graph[i + 1].add(j + 1)
            }
        }
        
        for (i in 1..n) {
            if (!visited[i]) {
                bfs(i)
                answer++
            }
        }
        
        return answer
    }
    
    fun bfs(start: Int) {
        val queue : Queue<Int> = LinkedList()
        queue.add(start)
        visited[start] = true
        
        while(queue.isNotEmpty()) {
            val now = queue.poll()
            
            for (i in graph[now]) {
                if (!visited[i]) {
                    visited[i] = true
                    queue.add(i)
                }
            }
        }
    }
}