문제

Programmers Lv3, 네트워크

핵심

• 컴퓨터의 개수와 연결에 대한 정보가 담긴 2차원 배열이 주어질 때 네트워크의 개수를 반환하는 문제이다.
• 각 컴퓨터는 자신의 네트워크를 가지고, 연결이 되어 있을 때 같은 네트워크라고 판단한다. DFS와 BFS, Union-Find 알고리즘을 이용한 풀이 모두 다 가능하다.

DFS 풀이

• 노드를 차례로 방문하면서 해당 노드와 연결된 노드는 같은 네트워크라고 판단한다. 해당 노드를 처음 방문했는지 여부로 네트워크의 개수를 세는 방법이다.

import java.util.*;

class Solution {
    public int solution(int n, int[][] computers) {
        
        boolean[] isVisited = new boolean[n];
        
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            if (!isVisited[i]) {
                dfs(i, n, isVisited, computers);
                ++ans;
            }
        }
        
        return ans;
    }
    
    void dfs(int cur, int n, boolean[] isVisited, int[][] computers) {
        isVisited[cur] = true;
        for (int i = 0; i < n; ++i) {
            if (!isVisited[i] && computers[cur][i] == 1) {
                dfs(i, n, isVisited, computers);
            }
        }
    }
}

시간 복잡도

• $O(V + E)$

BFS 풀이

• DFS와 접근 방식이 같다. 차이점은 스택에서 큐 자료구조로 바뀐다는 데 있다.

import java.util.*;

class Solution {
    public int solution(int n, int[][] computers) {
        
        boolean[] isVisited = new boolean[n];
        
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            if (!isVisited[i]) {
                bfs(i, n, isVisited, computers);
                ++ans;
            }
        }
        
        return ans;
    }
    
    void bfs(int st, int n, boolean[] isVisited, int[][] computers) {
    
        Queue<Integer> q = new LinkedList<>();
        isVisited[st] = true;
        q.add(st);
        while (!q.isEmpty()) {
            int cur = q.poll();
            for (int nxt = 0; nxt < n; ++nxt) {
                if (!isVisited[nxt] && computers[cur][nxt] == 1) {
                    isVisited[nxt] = true;
                    q.add(nxt);
                }
            }
        }
    }
}

시간 복잡도

• $O(V + E)$

Union-Find 풀이

• Union-Find 알고리즘은 여러 노드가 존재할 때 어떤 두 노드가 같은 집합에 있는지 확인하고, 같은 집합에 있다면 이를 서로 연결해 주는 알고리즘이다.
• 기본적으로 parent와 rank 배열 두 개를 쓰나, parent 배열을 -1로 초기화하고 음수 값을 트리 깊이로 본다면 하나의 parent 변수만 써도 충분하다.
• 시간복잡도는 아커만 역함수로 n이 매우 커도 아주 천천히 증가한다. 현실적인 범위에서 상수 시간을 보장한다.

import java.util.*;

class Solution {
    public int solution(int n, int[][] computers) {
        
        int[] p = new int[n];
        Arrays.fill(p, -1);
        
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i != j && computers[i][j] == 1) {
                    unionByRank(i, j, p);
                }
            }
        }
        
        Set<Integer> ans = new HashSet<>();
        for (int i = 0; i < n; ++i) {
            ans.add(find(i, p));
        }
        
        return ans.size();
    }
    
    int find(int x, int[] p) {
	    if (p[x] < 0) return x;
	    else return p[x] = find(p[x], p);
    }
    
    void unionByRank(int x, int y, int[] p) {
        x = find(x, p);
        y = find(y, p);
        if (x == y) return ;
        if (p[x] == p[y]) p[x]--;
        if (p[x] < p[y]) p[y] = x;
        else p[x] = y;
        return ;
    }
}

시간복잡도

• $O(V^2)$