[Algorithm] 네트워크

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

 

풀이

1. visited 테이블을 만든다. (방문처리)

2. computers 그래프를 탐색하면서 연결되어 있고 아직 방문하지 않은 노드에 대해서 연결된 노드를 모두 방문처리하도록 한다. (하나의 네트워크로 인식)

3. 하나의 네트워크를 방문처리 하면 네트워크 갯수 +1

 

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