[프로그래머스] 네트워크 (Lv 3)

 

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

코딩테스트 연습 - 네트워크

Union and Find 사용

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int g[201]={0};
int check[201]={0};

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

void Union(int x, int y) {
    x=find(x);
    y=find(y);
    if(x!=y) g[x]=y;
}

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    for(int i=0;i<n;i++) g[i]=i;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(i==j) continue;
            else {
                if(computers[i][j]==1) {
                    Union(i,j);
                }
            }
        }
    }
    for(int i=0;i<n;i++) {
        g[i]=find(i);
    }
    sort(g,g+n);
    int init=-1;
    for(int i=0;i<n;i++) {
        if(init!=g[i]) {answer++; init=g[i];}
    }
    return answer;
}

 

DFS

#include <string>
#include <vector>

using namespace std;
int check[200] = {0};

void dfs(int cur, int n, int cnt, vector<vector<int>> computers) {
    check[cur]=1;
    for(int next=0;next<n;next++) {
        if(check[next]==0 && computers[cur][next]==1 && cur!=next) {
            dfs(next,n,cnt,computers);
        }
    }
}

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

 

JS

let check = [];

function dfs(cur,n,cnt,computers) {
    check[cur]=1;
    for(let next=0;next<n;next++) {
        if(check[next]==0 && computers[cur][next]==1 && cur!=next) {
            dfs(next,n,cnt,computers);
        }
    }
}

function solution(n, computers) {
    var answer = 0;
    for(let i=0;i<n;i++) check.push(0);
    for(let i=0;i<n;i++){
        if(check[i]==1) continue;
        else dfs(i,n,++answer,computers);
    }
    return answer;
}