[프로그래머스] 네트워크

문제 링크

1. 문제 해결

전형적인 DFS/BFS 유형의 문제이다. 필자는 BFS를 이용하여 문제를 해결하였다.

2. 소스 코드

import java.util.*;
class Solution {    
    public int solution(int n, int[][] computers) {
        return bfs(computers,n);
    }
    
    private static int bfs(int [][] computers, int n){
        boolean[][] visited = new boolean[n][n];
        
        Queue<Integer> q = new LinkedList<>();
        
        int ret =0 ;
        for(int i =0 ; i < n ; i++){
            if(!visited[i][i]){
                visited[i][i] = true;
                q.add(i); //시작점
                ret++;
                
                while(!q.isEmpty()){
                    int cur = q.poll();
                    
                    for(int j =0 ; j < n ; j++){
                        if(!visited[cur][j] && computers[cur][j] == 1){
                            visited[cur][j] = visited[j][cur] = visited[j][j] = true;
                            q.add(j);
                        }
                    }
                }
            }
        }
        
        return ret;
    }
}