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

문제 링크

---

프로그래머스

접근 방법

---

A와 B가 연결되어 있고 B와 C가 연결되어 있을 때, A와 C도 연결되어 있다에서

Union-Find로 접근해 보기로 했습니다.

소스 코드

---

#include <string>
#include <vector>

using namespace std;

int *uf;

int find_root(int n)
{
    if (uf[n] == n)
        return n;
    return uf[n] = find_root(uf[n]);
}

void union_find(int x, int y)
{
    int parentX, parentY;
    
    parentX = find_root(x);
    parentY = find_root(y);
    
    uf[parentY] = parentX;
}

int solution(int n, vector<vector<int>> computers)
{
    uf = new int[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 (computers[i][j])
                union_find(i, j);

    int answer = 0;
    for (int i = 0; i < n; i++)
        if (uf[i] == i)
            ++answer;

    return answer;
}

코드 설명

---

computers[i][j] 가 1이면 i와 j가 연결되어 있다는 뜻이므로 i와 j를 Union-Find 합니다.

그다음 uf[i] == i를 만족하는 개수를 세어 총 네트워크의 수를 세어줍니다.

 

BFS와 DFS로도 풀 수 있습니다. 다음은 BFS 코드와 DFS 코드입니다.

소스 코드

---

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

using namespace std;

int *visited;

void bfs(vector<vector<int>> &computers, int n, int x)
{
    queue<int> q;
    q.emplace(x);
    visited[x] = 1;
    
    while (!q.empty())
    {
        int s = q.front();
        q.pop();
        
        for (int i = 0; i < n; i++)
        {
            if (s != i && computers[s][i] && !visited[i])
            {
                q.emplace(i);
                visited[i] = 1;
            }
        }
    }  
}

int solution(int n, vector<vector<int>> computers) 
{
    int answer = 0;
    visited = new int[n] {0};
    
    for (int i = 0; i < n; i++)
    {
        if (!visited[i])
        {
            bfs(computers, n, i);
            ++answer;
        }
    }
    
    return answer;
}

#include <string>
#include <vector>

using namespace std;

int *visited;

void dfs(vector<vector<int>> &computers, int n, int idx)
{
    visited[idx] = 1;
    
    for (int i = 0; i < n; i++)
    {
        if (i != idx && computers[idx][i] && !visited[i])
        {
            visited[i] = 1;
            dfs(computers, n, i);
        }
    }
}

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