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

 

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

프로그래머스

 

2개의 네트워크가 존재

1개의 네트워크가 존재

입력받은 노드들을 연결시켜서 연결된 집합의 갯수를 찾는 문제입니다.

선택한 문제 분류는 BFS/DFS였지만 그림을 보자마자 Union-Find가 먼저 생각이 났습니다.

그래서 우선은 Union-Find를 이용한 구현을 하였습니다.

 

1.n*n의 양방향 그래프이므로 굳이 컴퓨터의 연결상태 2차원 배열인 computers를 n^2의 배열을 돌 필요 없이 반인 (n^2)/2만 돌면서 union을 한다.

 

2.for문을 통해 배열을 돌면서 방문표시가 안된 번호에 들어가 방문표시를 하고 network의 갯수를 +1한다.

 

3.해당 번호와 union되어있는 번호들을 방문표시한다.     

 

이런식으로 하면 집합의 갯수를 구할 수 있습니다.

#include <string>
#include <vector>
using namespace std;
int root[202];
bool visit[202];
void init(int n)
{
    for(int i=0;i<=n;i++) root[i]=i;
}
int find(int a)
{
    if(a==root[a]) return a;
    else return root[a]=find(root[a]);
}
void uni(int a,int b)
{
    a=find(a);
    b=find(b);
    root[b]=a;
}
int solution(int n, vector<vector<int>> computers) 
{
    int answer = 0;
    init(n);
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<i;j++)
        {
            if(computers[i][j]) uni(i+1,j+1);
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(visit[i]) continue;
        visit[i]=1;
        answer++;
        for(int j=i+1;j<=n;j++)
        {
            if(find(i)==find(j)) visit[j]=1;
        }
    }
    return answer;
}

 

풀고보니 선택한 이 문제의 원래 분류는 DFS/BFS였던게 생각났습니다.

제작자의 의도에 맞게 문제를 풀기 위해 DFS로도 구현을 했습니다.

 

위의 Union-Find와 결과확인 방법은 비슷합니다. 마찬가지로 방문 체크를 통해 집합의 갯수를 구합니다.

그러나 방문체크를 하는 방법이 달라지게 됩니다.

 

1. 배열을 돌면서 방문체크가 되어있지 않은 번호에 들어가 방문 표시를 하고 network의 갯수를 +1한다. 그리고 DFS 함수에 현재 선택된 번호를 건내준다.

 

2. DFS함수에서 해당 번호와 연결돼있으면서 방문하지 않은 번호를 선택해서 방문체크를 하고 DFS함수에 건내준다(재귀)

 

3. 1번의 for문에서 선택된 번호의 DFS를 마치면 해당 번호와 연결된 번호들은 모두 방문체크가 된다.

 

4. 그리고 남은 번호들 중 방문체크가 되지 않은 번호에서 1번의 과정을 반복하면 집합의 갯수를 알 수 있다 

 

#include <string>
#include <vector>
bool visit[202];
int answer;
using namespace std;
void DFS(int a,int n, vector<vector<int>> computers)
{
    for(int i=0;i<n;i++)
    {
        if(computers[a][i]&&!visit[i])
        {
            visit[i]=1;
            DFS(i,n,computers);
            
        }
    }
}
void go(int n, vector<vector<int>> computers)
{
    for(int i=0;i<n;i++)
    {
        if(visit[i]) continue;
        visit[i]=1;
        answer++;
        DFS(i,n,computers);
    }    
}
int solution(int n, vector<vector<int>> computers) 
{
    go(n,computers);
    return answer;
}