LV3 네트워크 (Java)

 

---

 

문제

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

프로그래머스

 

풀이

나는 유니온 파인드를 활용하여 문제를 풀이하였다.

 

연결되어 있는 컴퓨터를 확인하고, union을 진행했다.

 

union find알고리즘 그대로 사용하면 풀 수 있는 문젠데, 마지막에 parent의 원소값으로 판단하는게 아닌 "find_parent" 함수를 실행하여 루트값을 확인해야한다. 

 

코드

import java.util.*;
import java.util.stream.*;

class Solution {
    
    public int find_parent(int[] parent, int x){
        if(parent[x] != x){
            parent[x] = find_parent(parent, parent[x]);
        }
        return parent[x];
    }
    
    public void union_parent(int[] parent, int a, int b){
        a = find_parent(parent, a);
        b = find_parent(parent, b);
        
        if(a<b){
            parent[b] = a;
        } else{
            parent[a] = b;
        }
    }
    
    public int solution(int n, int[][] computers) {
        
        int[] parent = IntStream.range(0, n).toArray();
        Set<Integer> s = new HashSet<>();
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(computers[i][j] == 1){
                    if(find_parent(parent, i) != find_parent(parent, j)){
                        union_parent(parent, i, j);
                    }
                }        
            }
        }
        
        for(int i=0; i<n; i++) s.add(find_parent(parent, i));
        
        return s.size();
    }
}

 

후기

 

- 사실 그냥 DFS로 방문 여부를 따져서 쉽게 풀 수 있다.

 

- union find알고리즘에서 parent 루트값은 항상 find_parent로 찾아야 한다. 잊지말자..