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

오늘의 학습 키워드

   - 알고리즘

   - 그래프 탐색

   - 유니온-파인드

공부한 내용 본인의 언어로 정리하기

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

유니온 파인드 + 그래프 탐색 알고리즘이 합쳐진 문제를 풀었다.

아이디어가 바로 떠올라서 금방 풀었다.

 

풀이 과정은 다음과 같다.

1. union-find 코드 작성

1 - 1. union(a, b) : a와 b집합이 있을때 두 집합을 합치는 연산

1 - 2. find(a) : a집합의 부모는 누구인지 확인하는 연산

2. 제공된 그래프를 반복문을 돌며 연결되었다면 union

2 - 1. 이 때 computers[i][j] = computers[j][i]이므로 반복문을 돌 때 아래와 같은 범위만 계산하면 됨

3. 모든 그래프에 대한 네트워크가 만들어졌다면, 모든 컴퓨터에 대해 반복문을 돌며 find 연산으로 중복을 제외한 모든 네트워크를 구하기 위해 set에 추가

 

풀이는 다음과 같다.

import java.util.*;

class Solution {
    
    int[] parents;

    public int solution(int n, int[][] computers) {
        
        parents = new int[n];
        
        for (int i = 0; i < n; i++) parents[i] = i;
        
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (i == j) continue;
                if (computers[i][j] == 1) union(i, j);
            }
        }
        
        HashSet<Integer> networkSet = new HashSet<>();
        for (int parent : parents) {
            networkSet.add(find(parent));
        }
        
        return networkSet.size();
    }
    
    boolean union(int a, int b) {
        
        int parentA = find(a);
        int parentB = find(b);
        
        if (parentA == parentB) return false;
        
        parents[parentA] = parentB;
        return true;
    }
    
    int find(int a) {
        if (parents[a] == a) return a;
        return parents[a] = find(parents[a]);
    }
    
}