프로그래머스[programmers] - 네트워크(Kotlin)[LV3]

문제

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

프로그래머스

 

문제 풀이

풀고 나서 Lv3가 맞나..? 싶은 문제였다.

인접행렬을 사용해서 풀면 쉽게 풀 수 있는 문제지만 Lv3라서 뭔가 복잡하게 풀어야 될 거 같아서

나름대로 복잡하게(?) 풀었다.

 

문제에서 요구하는 바는 연결할 수 있을 만큼 최대한으로 연결하고, 연결된 그룹의 수를 구하는 것이다.

여러 가지 방법이 있겠지만, 나는 노드를 구현해서 풀어보고 싶어서 해당 방식으로 풀었다.

 

우선 크게 노드를 가지는 map이 있다.

map에는 value와 , node를 저장했다.

해당 맵은 노드를 관리하는 Map이라고 생각하면 편할 것이다.

각 노드는 연결된 노드를 가지는 list를 가지고 있다.

문제에서 말하는 computer [i][j]가 1이라면 i 노드의 j노드가 추가되고, j 노드의 i가 추가된다.

이렇게 노드들을 전부 다 추가하고, 

전체 노드리스트에서 탐색을 시작한 시점에서 연결된 모든 노드들을 방문체크하고,

탐색을 시작한 노드의 개수를 계산한다.

탐색을 시작한 노드의 개수가 네트워크의 개수라고 생각하면 된다.

 

전체 코드

import java.util.*
import java.io.*
class Solution {
    val nodeList = mutableMapOf<Int,Node>()
    lateinit var visit : Array<Boolean>
    data class Node(val value : Int){
        val list = mutableListOf<Node>()
    }
    
    fun containNode(value : Int){
        if(!nodeList.contains(value)){
            nodeList[value]=Node(value)
        }
    }
    fun addEdge(from : Int, to: Int){
        val fromNode = nodeList[from]
        if(fromNode==null) return
        val toNode = nodeList[to]
        if(toNode == null) return 
        fromNode.list.add(toNode)
        toNode.list.add(fromNode)
    }
    fun solution(n: Int, computers: Array<IntArray>): Int {
        var answer = 0
        visit = Array(n){false}
        for(i in 0 until n){
            containNode(i) //i노드가 있는지 확인함.
            for(j in i+1 until n){
                if(!nodeList.contains(j)){
                    nodeList[j] = Node(j) //노드 생성
                }
                if(computers[i][j]==1){ //연결됨
                    computers[j][i]=0 //방문처리
                    computers[i][j]=0 //방문 처리
                    addEdge(i,j)      //연결
                }
            }
        }
        for(node in nodeList){
            if(visit[node.key])
                continue
            visit[node.key]=true
            for(item in node.value.list){
                if(visit[item.value])                
                    continue
                visit[item.value]=true
                search(item)
            }
            answer++
        }
        return answer
    }
    fun search(node : Node){
        for(item in node.list){
            if(visit[item.value])
                continue
            visit[item.value]=true
            search(item)
        }
    }
}