프로그래머스 (C/C++, Java) 43162 : 네트워크

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

프로그래머스

 

---

풀이

dfs로 현재 방문하지 않은 노드를 확인한 후, 해당 노드와 연결된 모든 노드들을 방문처리 한다.

위의 작업을 할 때마다 네트워크의 개수를 늘려가며 네트워크를 찾는다.

---

C/C++ 코드

#include <string>
#include <vector>

using namespace std;

bool visited[200] = {false, };
void dfs(vector<vector<int>>& computers, int n, int now) {
    visited[now] = true;
    for (int i = 0; i < n; i++) {
        if (computers[now][i] && !visited[i])
            dfs(computers, n, i);
    }
}

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

 

Java 코드

class Solution {
    boolean[] visited;
    
    private void dfs(int[][] computers, int n, int now) {
        visited[now] = true;
        for (int i = 0; i < n; i++) {
            if (computers[now][i] == 1 && !visited[i])
                dfs(computers, n, i);
        }
    }
    public int solution(int n, int[][] computers) {
        int answer = 0;
        visited = new boolean[n];
        
        for (int i = 0; i < n; i++) {
            if (visited[i]) continue;
            dfs(computers, n, i);
            answer++;
        }
        return answer;
    }
}