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

1. 문제

https://school.programmers.co.kr/learn/courses/30/lessons/43162

프로그래머스

 

2. 풀이

2-1. 문제 읽고 이해하기

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미

• 컴퓨터 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

 

2-2. 재정의와 추상화

컴퓨터는 노드(정점), 네트워크는 간선으로 치환해서 보면 결국 그래프의 갯수를 구하는 문제가 된다.

네트워크의 갯수를 알기 위해서는 연결 그래프가 몇 개인지 반환하면 된다.

 

2-3. 계획 세우기

2가지 방법으로 풀 수 있을 것 같다.

1. DFS, BFS를 이용해서 하나의 트리를 탐색 후 다음 트리를 탐색할 때마다 트리 갯수+1
2. union-find를 이용해서 그룹을 묶고, map에 <root_num, num_of_node> 이렇게 key-value로 묶어서 root_num에 소속된 노드가 몇 개인지 cnt -> map의 size를 반환

문제의 유형이 dfs/bfs이므로 1의 방법으로 먼저 풀어본 후, 2의 방법으로 풀어봐야겠다.

 

3. 코드

bfs를 이용한 풀이

#include <string>
#include <vector>
#include <queue>

using namespace std;

void bfs(int start, vector<bool> &visited, const vector<vector<int>> &computers){
    queue<int> q;
    q.push(start);
    while(!q.empty()){
        int curr = q.front();
        q.pop();
        for(int i=0; i<computers[curr].size(); i++){
            int connection = computers[curr][i];
            // 연결이 없거나 이미 방문한 노드는 재방문x
            if(connection==0 || visited[i]) continue;
            q.push(i);
            visited[i] = true;
        }
    }
}

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    vector<bool> visited(n, false);
    for(int i=0; i<n; i++){
        // 방문한 노드는 재방문하지 않는다.
        if(visited[i]) continue;
        answer++;
        bfs(i, visited, computers);
    }
    return answer;
}

 

dfs를 이용한 풀이

#include <string>
#include <vector>

using namespace std;

void dfs(int node, vector<bool> &visited, const vector<vector<int>> &computers){
    // 방문 체크
    visited[node]=true;
    
    // node 컴퓨터의 연결 정보를 쭉 살피기
    for(int i=0; i<computers[node].size(); i++){
        // node와 i컴퓨터의 연결정보
        int connection = computers[node][i];
        // 연결x || 이미 방문한 노드일 경우 재방문x
        if(connection==0 || visited[i]) continue;
        dfs(i, visited, computers);
    }
}

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    vector<bool> visited(n, false);
    for(int i=0; i<n; i++){
        if(visited[i]) continue;
        dfs(i, visited, computers);
        answer++;
    }
    return answer;
}

 

union-find를 이용한 풀이

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

using namespace std;

int myFind(int x, vector<int> &uf){
    if(uf[x]==x) return x;
    return uf[x] = myFind(uf[x], uf);
}

void myUnion(int x, int y, vector<int> &uf){
    x = myFind(x, uf), y = myFind(y, uf);
    if(x==y) return;
    uf[x]=y;
}

int solution(int n, vector<vector<int>> computers) {
    // uf 벡터 생성 및 초기화
    vector<int> uf(n);
    for(int i=0; i<n; i++){
        uf[i]=i;
    }
    
    for(int i =0; i<n; i++){
        for(int j=0; j<n; j++){
            if(i==j) continue;
            if(computers[i][j]==0) continue;
            myUnion(i, j, uf);
        }
    }
    
    // 그룹이 몇 개인지 알아보기 위함
    map<int, int> rootInfo; // {root, connection_cnt}
    for(int i=0; i<n; i++){
        rootInfo[myFind(i, uf)]++;
    }
    
    return rootInfo.size();
}