프로그래머스 Lv. 3 네트워크 JAVA

링크텍스트

설명

백준 2606번 바이러스와 유사한 문제이다. 링크텍스트
[[1, 1, 0], [1, 1, 0], [0, 0, 1]] 이게 뭔 소리인지 처음에 이해하지 못했다. 찾아보니
내가 백준에서 많이 사용했던 arr[a][b]=arr[b][a] =1 를 직관적으로 보여준 것이었다.
행 = 컴퓨터 번호
열 = 다른 컴퓨터와의 연결 상태이다.
그래서 첫 행이 [1,1,0]이면 자기자신과 1번이 연결되어있고 2번은 연결되어있지 않다는 것이다.
시간복잡도: O(N²), 공간복잡도: O(N)

회독

• [ x ] 1회
• 2회
• 3회

JAVA코드

class Solution {
        static boolean [] check;
    public int solution(int n, int[][] computers) {
        int answer = 0;
        check = new boolean[n+1];

        for(int i=0;i<n;i++){
            if(!check[i]){
                dfs(i, computers);
                answer++;
            }
        }
        
        return answer;
    }
    
    public static void dfs(int start, int [][] computers){
        check[start] = true;
        
        for(int i=0;i<computers.length;i++){
            if(computers[i][start]==1 && !check[i]){
                dfs(i,computers);
            }
        }
    }
}

다른 사람의 풀이

링크텍스트