[Programmers] 네트워크

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

프로그래머스

 

1. Python

def solution(n, computers):
    visited = set()
    def dfs(i):
        if i in visited:
            return
        visited.add(i)
        for j in range(n):
            if computers[i][j] == 1:
                dfs(j)
    ret = 0
    for i in range(n):
        if i not in visited:
            dfs(i)
            ret += 1
    return ret

 

2. C++

void dfs(int n, const vector<vector<int>>& computers, set<int>& visited, int i) {
	if (visited.find(i) != visited.end()) return;
	visited.insert(i);
	for (int j=0; j<n; j++) {
		if (computers[i][j] == 1) {
			dfs(n, computers, visited, j);
		}
	}
}

int solution(int n, vector<vector<int>> computers) {
    int ret {0};
	set<int> visited;
	for (int i=0; i<n; i++) {
		if (visited.find(i) == visited.end()) {
			dfs(n, computers, visited, i);
			ret++;
		}
	}
	return ret;
}