프로그래머스 3레벨 - 네트워크

문제

---

 

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

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

 

 

 

제한사항

---

컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.
각 컴퓨터는 0부터 n-1인 정수로 표현합니다.
i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다.
computer[i][i]는 항상 1입니다.

 

 

입출력 예

---

n	computers	return
3	[[1, 1, 0], [1, 1, 0], [0, 0, 1]]	2
3	[[1, 1, 0], [1, 1, 1], [0, 1, 1]]	1

 
  

 

나의 생각

---

노드 클래스와 네트워크 클래스를 만들고, 노드 클래스의 배열을 네트워크 클래스에서 관리하게끔 만드려고 하였습니다.

노드 클래스에는 각 노드의 연결정보가 들어있게끔 설계하였으나, 반복문의 과정에서 뭔가 값들이 꼬이기 시작하였고, 클래스를 여러개 쓸 필요 없이 단순 2중 배열을 이용하여 BFS를 사용할 수 있다는 것을 알게 되었습니다. 해당 방법을 이용하여 노드의 배열 대신 Int배열을 이용하여 이중 배열을 만들고, 자기자신을 제외한 노드들을 각 리스트에 넣어주었습니다.

문제에서 컴퓨터는 최소 1대이므로, 자기자신은 무조건 연결이 되어있어야 하고, 시작노드를 0번으로 넣어 BFS 함수를 짜 처리해주었습니다.

 

 

코드

---

import java.util.*
import kotlin.collections.ArrayList

class Solution {
    lateinit var visited: BooleanArray
    lateinit var link: ArrayList<ArrayList<Int>>


    fun bfs(start : Int){
        val q: Queue<Int> = LinkedList()
        q.add(start)
        visited[start] = true

        while(q.isNotEmpty()){
            val value = q.poll()
            val targetLinks = link[value]
            for(i in targetLinks){
                if(!visited[i]) {
                    visited[i] = true
                    q.add(i)
                }
            }
        }
    }

    fun solution(n: Int, computers: Array<IntArray>): Int {
        var answer = 0
        visited = BooleanArray(n) {false}
        link = ArrayList(n)


        for (i in 0 until n) {
            link.add(ArrayList())
            for (j in 0 until n) {
                if (computers[i][j]==1 && i != j) {
                    link[i].add(j)
                }
            }
        }

        for (i in 0 until n) {
            if (!visited[i]) {
                bfs(i)
                answer++
            }
        }
        return answer
    }


}