[프로그래머스] 네트워크

https://programmers.co.kr/learn/courses/30/lessons/43162?language=java 

코딩테스트 연습 - 네트워크

---

 

풀이

두가지 방법의 풀이가 있다. Union-Find 알고리즘을 사용하는 방법과 BFS를 사용하는 방법 두가지가 있다.

 

1. Union-Find 알고리즘

인접행렬로 주어진 정보를 이용해서 i!=j && computers[i][j]==1 이라면 두 컴퓨터 사이에는 네트워크로 연결이 된것이므로, i와 j를 Union 해준다.

 

모든 노드들을 Union-Find 해준 뒤, 0~N-1번 노드를 탐색하며 큰 덩어리의 개수(i==parent[i] 인 노드의 개수) 를 세어준다.

 

2. BFS

모든 노드를 탐색하며, 탐색한 노드를 visited배열로 체크를 해주며, 방문하지 않은 노드이면서 현재 노드와 연결이 된 노드들을 탐색해준다. 모두 탐색을 하며 한번 BFS를 탐색할때마다 ANSWER+1을 해준다.

 

코드

1. Union-Find

class Solution {
    static int parent[]=new int[200];
    public void init(int n){
        for(int i=0;i<n;i++) parent[i]=i;
    }
    public int find_parent(int c){
        if(c==parent[c]){
            return c;
        }
        else{
            return find_parent(parent[c]);
        }
    }
    public void union_parent(int a,int b){
        a=find_parent(a);
        b=find_parent(b);
        
        if(a>b){
            parent[a]=b;
        }
        else{
            parent[b]=a;
        }
    }
    public int solution(int n, int[][] computers) {
        int answer = 0;
        init(n);
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(i!=j && computers[i][j]==1){
                    union_parent(i,j);
                }
            }
        }
        for(int i=0;i<n;i++){
            if(parent[i]==i) answer++;
        }
        return answer;
    }
}

 

2. BFS

import java.util.*;
class Solution {
    static boolean visited[]=new boolean[200];
    public void bfs(int node,int n,int[][] computers){
        Queue<Integer> q=new LinkedList<Integer>();
        q.offer(node);
        visited[node]=true;
        
        while(!q.isEmpty()){
            int now=q.poll();
            
            for(int i=0;i<n;i++){
                if(i!=now && computers[now][i]==1 && !visited[i]){
                    q.offer(i);
                    visited[i]=true;
                }
            }
        }
    }
    public int solution(int n, int[][] computers) {
        int answer = 0;
        for(int i=0;i<n;i++){
            if(!visited[i]){
                bfs(i,n,computers);
                answer++;
            }
        }
        return answer;
    }
}