99클럽 코테 스터디 31일차 TIL / [프로그래머스] 네트워크

오늘의 학습 키워드

---

Union-Find

문제

---

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

• 플랫폼: 프로그래머스
• 문제명: 네트워크
• 난이도: Lv3

풀이

---

import java.util.*;

class Solution {
    
    static int[] parent;
    
    public int solution(int n, int[][] computers) {
        parent = new int[n];
        
        for(int i=0; i<n; i++) {
            parent[i] = i;
        }
        
        for(int i=0; i<n; i++) {
            for(int j=i+1; j<n; j++) {                
                if(computers[i][j] == 1) {
                    union(i, j);    
                }
            }
        }
        
        Set<Integer> set = new HashSet<>();
        for(int i=0; i<n; i++) {
            set.add(find(i));
        }
        
        return set.size();
    }
    
    public void union(int x, int y) {
        int px = find(x);
        int py = find(y);
        
        parent[py] = px;
    }
    
    public int find(int x) {
        if(parent[x] == x) {
            return x;
        }
        
        return parent[x] = find(parent[x]);
    }
}

접근

• 서로 연결되지 않은 그래프 집합 개수를 구하는 문제로, Union-Find 알고리즘을 통해 구현했습니다.
• 문제에서 주어진 computers 배열의 값이 1이라면 서로 연결되었다는 것을 의미하므로, 배열을 순회하며 값이 1일때 union 연산을 해주었습니다.

  for(int i=0; i<n; i++) {
      for(int j=i+1; j<n; j++) {                
          if(computers[i][j] == 1) {
              union(i, j);    
          }
      }
  }

• union 연산이 모두 끝났다면, Union-Find 연산 결과가 담긴 parent 배열을 순회하며 집합의 개수를 구합니다.

  Set<Integer> set = new HashSet<>();
  for(int i=0; i<n; i++) {
      set.add(find(i));
  }

• 해당 집합의 크기가 네트워크의 개수가 됩니다.

  return set.size();

소요 시간

30분