Programmers[43162] - 네트워크[Level3]

링크

프로그래머스

문제설명

• 그래프 연결된 네트워크 개수구하기

문제풀이

• DisjointSet 개수
• BFS,DFS

문제코드_DisjointSet

public class Solution43162_네트워크_DisjointSet {

    public static int[] parent;

    public static void MakeSet(int a) {
        parent[a] = - 1;
    }

    public static int FindSet(int a) {
        if(parent[a]<0) return a;
        else {
            parent[a] = FindSet(parent[a]);    //경로압축
        }
        return parent[a];
    }

    public static void Union(int a, int b) {
        int root1 = FindSet(a);
        int root2 = FindSet(b);

        if(root1==root2) {
            return;
        }
//        a<-b
        parent[root2] = root1;
    }

    public static int solution(int n, int[][] computers) {
        parent = new int[n];
        for (int i = 0; i < n; i++) {
            MakeSet(i);
        }

        for (int from = 0; from < n; from++) {
            for (int to = 0; to < n; to++) {
                if(computers[from][to]==1) {
                    Union(from,to);
                }
            }
        }

        int answer = 0;
        for (int i = 0; i < n; i++) {
            if(parent[i]<0)answer++;
        }
        return answer;
    }

    public static void main(String[] args) {
        System.out.println(solution(3, new int[][] {
            {1, 1, 0},
            {1, 1, 0},
            {0, 0, 1}}));
        System.out.println(solution(3, new int[][] {
            {1, 1, 0},
            {1, 1, 1},
            {0, 1, 1}}));
    }
}

문제코드_BFS

import java.util.LinkedList;

public class Solution43162_네트워크_BFS {

    public static int solution(int n, int[][] computers) {
        int answer = 0;

        boolean[] visited = new boolean[n];
        for (int i = 0; i < n; i++) {
            if(!visited[i]) {
                answer++;
                LinkedList<Integer> q = new LinkedList<Integer>();
                q.add(i);
                visited[i] = true;

                int now;
                while(!q.isEmpty()) {
                    now = q.poll();
                    for (int next = 0; next < n; next++) {
                        if(computers[now][next]==1 && !visited[next]) {
                            visited[next] = true;
                            q.add(next);
                        }
                    }
                }
            }
        }

        return answer;
    }

    public static void main(String[] args) {
        System.out.println(solution(3, new int[][] {
            {1, 1, 0},
            {1, 1, 0},
            {0, 0, 1}}));
        System.out.println(solution(3, new int[][] {
            {1, 1, 0},
            {1, 1, 1},
            {0, 1, 1}}));
    }
}

아쉬운 점

• 뭔가 연결성검사는 DFS로 하기싫다.
• adj matrix에서 탐색 실수
  • nextnode 는 for문 반복문의 2차원인덱스(i)임
  • 2차원 인덱스의 값(computers[now][i])이 아니라

잘한 점

• BFS, DisjointSet으로 구현했음
  • N<=200이라 둘다 시간차이가 별로 없음
• DisjointSet 직접 구현했음
  • 경로압축만 구현했음
  • Rank기준 Union귀찮음