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

프로그래머스

 

문제



연결된 네트워크를 한 묶음으로 했을 때 몇개의 네트워크가 있는지 출력하는 문제이다.

---

풀이

입력은 2차원 배열로 주어지지만 한 네트워크가 다른 네트워크를 방문하면 다른네트워크가 방문한 것과 동일하게 처리하기때문에 1차원으로 생각하면 된다.

즉 한번 방문한 컴퓨터는 고려하지 않아도 된다.

 

먼저 방문여부를 저장해줄 visited를 1차원배열로 선언한다.

val visited = MutableList(n) {0}

0으로 초기화했으며 0은 미방문, 1은 방문을 의미한다.

 

이후 BFS에서 자기자신과 연결되어있는 컴퓨터를 저장할 stack을 선언한다.

 

val stack = mutableListOf<Int>()

 

그 후 BFS를 구현한다.

 

fun BFS(sr: Int) {
    cnt++
    visited[sr] = 1
    stack.add(sr)

    while (stack.size != 0) {
        val nr = stack.removeFirst()
        for ( i in 0 until n) {
            if (computers[nr][i] == 1 && visited[i] == 0) {
                stack.add(i)
                visited[i] = 1
            }          
        }
    }  
}

한 묶음 당 하나의 cnt이므로 BFS진입 시 cnt를 증가시켜준다.

이 후 현재 자기자신을 방문처리하고 스택에 입력한다.

스택이 빌때까지 반복하는데 현재 컴퓨터와 연결되어있는 컴퓨터를 뽑아 해당 컴퓨터를 방문하지 않았다면 스택에 넣고 방문처리한다.

BFS가 한번 실행되면 처음 입력된 컴퓨터와 연결되어있는 컴퓨터는 모두 방문처리된다.

for (i in 0 until n) {
    if (visited[i] == 0) {
        BFS(i)
    }
}

그 후 모든 컴퓨터를 돌며 방문하지 않았을 경우 BFS를 실행하여 cnt값을 갱신한다.

---

코드

class Solution {
    fun solution(n: Int, computers: Array<IntArray>): Int {
        var answer = 0
        val visited = MutableList(n) {0}
        var cnt = 0
        
        val stack = mutableListOf<Int>()
        
        
        
        fun BFS(sr: Int) {
            cnt++
            visited[sr] = 1
            stack.add(sr)
            
            while (stack.size != 0) {
                val nr = stack.removeFirst()
                for ( i in 0 until n) {
                    if (computers[nr][i] == 1 && visited[i] == 0) {
                        stack.add(i)
                        visited[i] = 1
                    }          
                }
            }  
        }
        for (i in 0 until n) {
            if (visited[i] == 0) {
                BFS(i)
            }
        }
       
        return cnt
    }
}