프로그래머스 dfs/bfs 네트워크문제

class Solution {
    var answer = 0

    var networkSheet = mutableSetOf<Int>()
    var checkVisit = mutableSetOf<Int>()
    fun solution(n: Int, computers: Array<IntArray>): Int {
        for (i in 0 until n){
            if(!networkSheet.contains(i)){
                linking(i,n,computers)
                answer++
            }
        }
        println(answer)
        return answer
    }

    fun linking(startP: Int,computersNum:Int,computers: Array<IntArray>){
        if (checkVisit.contains(startP)){
            return
        }else{
            checkVisit.add(startP)
            for (i in 0 until computersNum){
                if(computers[startP][i] ==1){
                    networkSheet.add(i)
                    linking(i,computersNum,computers)
                }
            }
        }
    }
}

 

내 풀이는

먼저

1) 링킹(linking)

 자신과 연결된 컴퓨터를 기록함

 그 기록된 컴퓨터도 linking을 재귀함수처럼 사용하여 연결된 모든것들을 기록함

 

2) 이러한 링킹을 0~n까지 실행하여 모든 컴퓨터의 네트워크 상황을 파악하는데 

네트워크에 포함되지 않았던 것들은 새로운 초기 네트워크를 만들어서 다시 시작

 

 

 

다른사람들의 풀이

class Solution {
    fun solution(n: Int, computers: Array<IntArray>): Int {
        var answer = 0
        val q=java.util.ArrayDeque<Int>()
        val visit=BooleanArray(n)

        for(i in 0 until n){
            if(!visit[i]){
                visit[i]=true
                answer++
                q.add(i)
                while(!q.isEmpty()){
                    val p=q.poll()
                    for(j in 0 until n){
                        if(p==j)    continue
                        if(!visit[j]&&computers[p][j]==1){
                            q.add(j)
                            visit[j]=true
                        }
                    }
                }   
            } 
        }     
        return answer
    }
}

 나랑 비슷한 풀이인것 같음 단지 만드는 형태가 다를뿐 for문을 3번쓴거랑 같구나

그래도 얻을거 있나 확인해봄

1. BooleanArray 

An array of booleans. When targeting the JVM, instances of this class are represented as boolean[].
Constructor:
Creates a new array of the specified size, with all elements initialized to false.

 

최초의 사이즈크기만큼의 false를 default로 하는 어레이를 생성하는것

 

2.ArrayDeque

양방향 큐라고 함

Resizable-array implementation of the {@link Deque} interface. Arraydeques have no capacity restrictions; they grow as necessary to support usage. They are not thread-safe; in the absence of external synchronization, they do not support concurrent access by multiple thread Null elements are prohibited. This class is likely to be faster than {@link Stack} when used as a stack, and faster than {@link LinkedList} when used as a queue.

 

fun main() {

val deque = ArrayDeque(listOf(1, 2, 3))

deque.addFirst(0)

deque.addLast(4)

println(deque) // [0, 1, 2, 3, 4]

println(deque.first()) // 0

println(deque.last()) // 4

deque.removeFirst()

deque.removeLast()

println(deque) // [1, 2, 3] }

 

이렇게 보니까 mutableList에도 removeFirst 이런거 사용이 가능했는데 프로그래머스 내부에서는 안돌아 가더라.. 

 

찾아보니까 mutableList처러 arrayDeque는 mutablelist로 컴파일 되기때문에 인덱스로도 접근이 가능하다고 한다.

 

뭔가 대단한 기능콜렉션인거 같다..