[프로그래머스 (Java)] 네트워크

 

https://programmers.co.kr/learn/courses/30/lessons/43162?language=java 

코딩테스트 연습 - 네트워크

i 번째 노드가 어떤 network 에 속하는지에 대한 정보를 담고 있는 network 배열을 생성합니다.

computers 배열을 순회하면서 network 배열을 업데이트 하는 makeNetwork 메서드를 작성합니다.

makeNetwork는 dfs 를 이용하여 input 으로 들어온 idx 와 연결되어 있는 모든 network 를 확인하고 만약 연결되어있다면 netNum 으로 network 값을 업데이트 합니다.

network 의 모든 배열이 업데이트가 완료될때까지 만든 network 개수를 답으로 반환합니다. 

class Solution {
    public void makeNetwork(int[][] computers, int[] network, int netNum, int idx) {
        network[idx] = netNum;
        int[] adjacent = computers[idx];
        for (int i = 0; i < adjacent.length; i++) {
            if (adjacent[i] == 1 && network[i] == 0) {
                makeNetwork(computers, network, netNum, i);
            }
        }
    }

    public int solution(int n, int[][] computers) {
        int answer = 0;
        int[] network = new int[n];

        for (int i = 0; i < n; i++) {
            if (network[i] == 0) {
                answer++;
                makeNetwork(computers, network, answer, i);
            }
        }

        return answer;
    }
}