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

문제 링크

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

 

 

 

풀이

DFS/BFS 파트에 있지만 문제를 보고 union-find가 먼저 떠올라서 union-find로 풀었다.

 

// 요약

 

// find_root()

- root를 찾아주는 재귀로 구현한 함수

 

// init

자신을 root로 설정

 

// process

인접행렬 computers가 대각선을 기준으로 대칭되므로 연산을 줄이기 위해 반복문을 최소한으로 돌게한다.

(i = 0~n-1일 때, j=i+1 ~ n이다)

{

    연결돼있다면, 각 i와 j의 root를 찾아주고 root 인덱스가 큰 정점을 root 인덱스가 작은 정점으로 연결한다.

}

 

최종적으로, root가 다른 것이 다른 네트워크 집합이므로 중복된 root를 제외하고 개수를 세어준다.

 

 

#include <string>
#include <vector>
#include <map>

using namespace std;

// 컴퓨터 개수 n
// 연결에 대한 정보 담긴 2차원 배열 computers

int find_root(map<int, int>& root, int n){      // root 찾기
    if(n == root[n]) return n;      // 자신이 root면 return
    return find_root(root, root[n]);        // 부모의 root찾기
}

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    
    // init
    map<int, int> root;     // for union-find
    for(int i=0; i<n; i++) root[i] = i;     // 자신을 root로 설정
    
    // process
    for(int i=0; i<n-1; i++){
        for(int j=i+1; j<n; j++){
            if(computers[i][j]==0) continue;
            int rootI = find_root(root, i);
            int rootJ = find_root(root, j);
             
            root[max(rootI, rootJ)] = min(rootI, rootJ);    // index가 큰 root = index 작은 root
        }
    }
    
    map<int, int> m;        // for 중복된 부모 개수 제거
    for(int i=0; i<n; i++){
        int rt = find_root(root, i);        // root
        m[rt]++;      // 중복된 root 개수 카운팅
    }
    answer = m.size();      // 네트워크 개수 == 노드 개수
    
    return answer;          // 네트워크 개수 리턴
}