Solution.java (Union-Find)

import java.util.*;

class Solution {
    int[] p;
    
    public int solution(int n, int[][] computers) {
        int answer = 0;
        
        p = new int[n];
        
        for (int i = 0; i < n; i++) p[i] = i;
        
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                if (computers[i][j] == 1) {
                    union(find(i), find(j));
                }
            }
        }
        
        HashSet<Integer> hs = new HashSet<>();
        for (int i : p) {
            hs.add(find(i));
        }
        
        answer = hs.size();
        
        return answer;
    }
    
    void union(int a, int b) {
        p[a] = b;
    }
    
    int find(int x) {
        if (p[x] == x) return x;
        
        return p[x] = find(p[x]);
    }
}

문제를 보고 Union-Find 알고리즘이 먼저 떠올라 풀었는데

다른 사람의 풀이를 보고 DFS 알고리즘으로도 한 번 풀어보았다.

Solution.java (DFS)

import java.util.*;

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

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges