[Programmers] 네트워크 - JAVA

📚 Problem

네트워크

• 컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수 찾기

📝 Solution

Key Idea

• union-find 를 이용해 구현
• 전체를 검사하여 1 인값이 있으면 union 합니다
• 하지만 최종 parent 배열에서 각 노드가 루트노드를 가리키지 않는 반례도 있는 것 같아
• for 문 돌려서 각 노드마다 find 값을 대입해줍니다
• 그리고 다른 네트워크의 개수를 세기 위해 Hashmap 을 이용하여 size 를 구합니다

    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 = 0; j < n; j++)
                if(j != i && computers[i][j] == 1)
                    union(i, j);

        for(int i = 0; i < n; i++)
            parent[i] = find(i);

        HashMap<Integer, Integer> map = new HashMap<>();

        for (int key : parent)
            map.put(key, map.getOrDefault(key, 0) + 1);

        return map.size();
    }

💻 Code

Solution.java

import java.util.HashMap;

class Solution {
    private 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 = 0; j < n; j++)
                if(j != i && computers[i][j] == 1)
                    union(i, j);

        for(int i = 0; i < n; i++)
            parent[i] = find(i);

        HashMap<Integer, Integer> map = new HashMap<>();

        for (int key : parent)
            map.put(key, map.getOrDefault(key, 0) + 1);

        return map.size();
    }

    private int find(int n) {
        if(parent[n] == n)
            return n;
        return parent[n] = find(parent[n]);
    }

    private void union(int a, int b) {
        int parent_a = find(a);
        int parent_b = find(b);

        if(parent_a < parent_b)
            parent[parent_b] = parent_a;
        else
            parent[parent_a] = parent_b;
    }
}

SolutionTest.java

import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.assertEquals;

public class SolutionTest {
    Solution solution;

    @BeforeEach
    public void setSol(){
        solution = new Solution();
    }

    @Test
    public void solution_1(){
        int result = solution.solution(3, new int[][]{{1,1,0},{1,1,0},{0,0,1}});
        assertEquals(2, result);
    }

    @Test
    public void solution_2(){
        int result = solution.solution(3, new int[][]{{1,1,0},{1,1,1},{0,1,1}});
        assertEquals(1, result);
    }
}