Programmers 43162 - 네트워크

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

프로그래머스

 

네트워크의 개수를 판정하는 문제이다.

여기서 네트워크란 직/간접적으로 연결 돼 있는 것들의 집합이다.

우선 n개의 노드가 있기 때문에 이 노드들의 방문 여부를 저장할 배열을 만든다.

그리고 시작점을 1~ n으로 해서 해당 시작점이 방문되지 않았다면 dfs를 한다.

여기에서 dfs가 진행된 횟수가 곧 네트워크의 개수를 알 수 있다.

왜냐하면 dfs가 끝났는데도 새롭게 시작한다는 것은 연결된 네트워크가 아니라 새로운 네트워크의 시작이라는 의미이기 때문이다.

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