[C++] Programmers Lv. 3 "네트워크"

🔵 문제 링크

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

프로그래머스

 

🔵 문제 접근

네트워크의 총 개수를 찾는 문제이다.

DFS를 활용하거나, union-find를 이용하여 연결된 노드들의 집합 수를 구할 수 있다.

 

🔵 DFS

solution에서의 DFS의 호출 횟수가 답이 된다.

#include <string>
#include <vector>

using namespace std;

vector<bool> visited;

// dfs
// 타고타고 들어간다.
void dfs(const vector<vector<int>>& network, int node)
{
    visited[node] = true;

    for (int i = 0; i < network[node].size(); i++)
        if (network[node][i] == 1 && !visited[i])
            dfs(network, i);
}

int solution(int n, vector<vector<int>> computers) 
{
    visited = vector<bool>(computers.size(), false);

    int answer = 0;

    for (int i = 0; i < n; i++)
    {
        if (!visited[i])
        {
            dfs(computers, i);
            answer++;
        }
    }

    return answer;
}

 

🔵 union-find

root의 개수가 곧 답이 된다.

#include <string>
#include <vector>

using namespace std;

// union - find
class DisjointSet
{
    vector<int> parent, rank;

public:
    DisjointSet(int size) : parent(size, -1), rank(size, 0) {}

    int Find(int node)
    {
        if (parent[node] == -1)
            return node;

        // 경로 압축
        return parent[node] = Find(parent[node]);
    }

    void MakeUnion(int node1, int node2)
    {
        int root1 = Find(node1);
        int root2 = Find(node2);

        if (root1 != root2)
        {
            if (rank[root1] < rank[root2])
                parent[root1] = root2;
            else if (rank[root2] < rank[root1])
                parent[root2] = root1;
            else
            {
                parent[root1] = root2;
                rank[root2]++;
            }
        }
    }

    int GetRootCount()
    {
        int rootCount = 0;
        for (int i = 0; i < parent.size(); i++)
            if (parent[i] == -1)
                rootCount++;

        return rootCount;
    }
};

int solution(int n, vector<vector<int>> computers) 
{
    int answer = 0;

    DisjointSet disjointSet(n);

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (computers[i][j] == 1)
                disjointSet.MakeUnion(i, j);

    answer = disjointSet.GetRootCount();

    return answer;
}