알고리즘 스터디 21일차

1. 네트워크

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입니다.

입출력 예

n 3
computers [[1, 1, 0], [1, 1, 0], [0, 0, 1]]
return 2
n 3
computers [[1, 1, 0], [1, 1, 1], [0, 1, 1]]
return 1

2) 문제 분석 및 풀이

1) 설계, 분석

처음 풀었을 때는 유니온 파인드로 풀었다.
그러나 공부하는 단원이 그래프이니.... 그래프를 통한 접근을 해보자
문제를 읽어보면 연결된 컴퓨터는 하나의 네트워크로 취급.
방문하지 않은 어떤 노드에서 BFS/DFS를 사용하면 해당 노드에 연결된 노드들이 생기고 이들은 같은 네트워크에 속함.
BFS/DFS가 를 시작하는 횟수가 정답.

2) 풀이

1. DFS

#include <string>
#include <vector>

using namespace std;
vector<bool> visited;

void RunDFS(int u, int vMax, vector<vector<int>>& computers)
{

    for (int v=0; v<vMax; v++)
    {
        if (visited[v]) continue;
        if (u==v) continue;
        if (computers[u][v] == 1)
        {
            visited[v] = true;
            RunDFS(v,vMax, computers);
        }

    }
}

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

    visited.resize(n, false);
    for (int i=0; i<n; i++)
    {
        if (visited[i]) continue;
        visited[i] = true;
        answer++;
        RunDFS(i,n, computers);
    }
    return answer;
}

2. Union - Find

#include <string>
#include <vector>

using namespace std;
vector<int> parents;
vector<int> ranks;

int find(int x)
{
    if (x == parents[x]) return x;
    return parents[x] = find(parents[x]);
}

void merge(int a, int b)
{
    int A = find(a);
    int B = find(b);

    if (A != B)
    {
        if (ranks[A] > ranks[B])
        {
            parents[B] = A;
        }
        else if (ranks[A] < ranks[B])
        {
            parents[A] = B;
        }
        else
        {
            parents[B] = A;
            ranks[A]++;
        }
    }
}

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    // 초기상태
    // 자신의 부모는 자기 자신
    ranks.resize(n,1);
    for (int i=0; i< n; i++)
    {
        parents.push_back(i);
    }

    // 간선의 두 노드를 union
    for (int i = 0; i < n; i++)
    {
        for (int j=0; j < n ; j++)
        {
            if (i == j) continue;
            if (computers[i][j] == 1)
            {
                merge(i , j);
            } 
        }
    }

    //루트 노드의 개수가 네트워크의 개수
    for (int i=0; i< n; i++)
    {
        if (find(i) == i) answer++;
    }

    return answer;
}