[문제풀이][3Level][JAVA] 프로그래머스 - 네트워크(BFS->Union-Find 풀이)

네트워크 문제

문제설명

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

 

제한사항

• 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.
• 각 컴퓨터는 0부터 n-1인 정수로 표현합니다.
• i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다.
• computer[i][i]는 항상 1입니다.

입출력 예

입출력 예 설명

예제 #1

아래와 같이 2개의 네트워크가 있습니다.

예제 #2

아래와 같이 1개의 네트워크가 있습니다.

 

풀이방법

프로그래머스에서 제공하는 코딩테스트 연습문제 Level 3 의 문제입니다. 일단 네트워크 문제는 분류가 깊이/너비 우선 탐색(DFS/BFS)로 분류가 되어있습니다. 하지만 저는 이 문제를 Union-Find로 풀어보려 합니다. 왜냐하면 연결된 그룹을 찾는 문제이고 주어진 입력값으로 각 컴퓨터를 연결하여 집합으로 묶어주면 그 집합의 개수만 카운트 해주면 될 것 같아서 저는 Union-Find 로 풀어보았습니다.

https://tylee82.tistory.com/291

[Java] Union-Find (유니온-파인드) 알고리즘

import java.util.*;

class Solution {
    
    static int[] uArr;
    
    public int solution(int n, int[][] computers) {
        int answer = 0;
        uArr = new int[n+4];
        
        for(int i=0; i<n ; i++){
            for(int j=0; j<n ; j++){
                if(i==j) continue; // computer[i][i]는 항상 1 이기때문에 필요없음
                if(computers[i][j]==1){ // 연결된 컴퓨터끼리 Union 해줌
                    setUnion(i, j); 
                }
            }
        }
        
        // System.out.println("0:"+getFind(0));
        // System.out.println("1:"+getFind(1));
        // System.out.println("2:"+getFind(2));
        
        // 집합의 개수를 카운트하기위한 변수
        ArrayList<Integer> alist = new ArrayList<Integer>();
        for(int i=0; i<n ; i++){
            if( alist.contains(getFind(i)) ){
                // getFind로 찾은 집합의 우두머리가 이미 alist 변수에 있으면 pass
                continue;  
            } 
            else {
                // alist 에 없으면 추가
                alist.add(getFind(i));
            }
        }
        
        // 집합은 alist 의 size 이다.
        answer = alist.size();
        
        return answer;
    }
    
    public void setUnion(int i, int j){
        int a = getFind(i);
        int b = getFind(j);
        if(a == b) return;
        uArr[a] = b;
    }
    
    public int getFind(int tar){
        if(uArr[tar] == 0) return tar;
        int ret = getFind(uArr[tar]);
        uArr[tar] = ret;
        return ret;
    }
}

 

결과