[프로그래머스/Level 3] 네트워크 (C++)

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

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

처음 DFS 진입이 몇번 일어나는지 구하면 되는 문제입니다.

 

#include <string>
#include <vector>
using namespace std;

bool visit[201];

void DFS(vector<vector<int>> computers, int idx, int n) {
    
    for(int i = 0; i < n; i++) {
        if(!visit[i] && computers[idx][i] == 1) {
            visit[i] = true;
            DFS(computers, i, n);
            // visit[i] = false;
        }
    }
}

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

 

/* Union&Find 풀이 */

#include <string>
#include <vector>
#include <set>
using namespace std;

int unf[201];
set<int> nodes;

int Find(int v) {
    if(v == unf[v]) return v;
    else return unf[v] = Find(unf[v]);
}

void Union(int a, int b) {
    int x, y;
    x = Find(a);
    y = Find(b);
    if(x != y) unf[x] = y;
}

int solution(int n, vector<vector<int>> computers) {
	// unf 배열 초기화
    for(int i = 0; i < n; i++) {
        unf[i] = i;
    }
    
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            if(computers[i][j] == 1) Union(i, j);
        }
    }
    
    for(int i = 0; i < n; i++) {
        nodes.insert(Find(i));
    }
    
    return nodes.size();
}