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

문제

programmers.co.kr/learn/courses/30/lessons/43162

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

 

코드

import java.util.*;

class Solution {
    static boolean[] visited;
    static int cnt;
    public static void bfs(int start, ArrayList<Integer>[] adjacent){
        Queue<Integer> q = new LinkedList<Integer>();
        q.offer(start);
        cnt++;
        
        while(!q.isEmpty()){
            int f = q.poll();
            visited[f] = true;
            for(int e : adjacent[f]){
                if(!visited[e]){
                    q.offer(e);
                    visited[e] = true;
                }
            }
        }        
    }
    public static int solution(int n, int[][] computers) {
        int answer = 0;
        ArrayList<Integer>[] adjacent = new ArrayList[n+1];
        visited = new boolean[n+1];
        cnt = 0;
        for(int i=1; i<=n; i++) {
        	adjacent[i] = new ArrayList<Integer>();
        }
        for(int i=1; i<=n; i++){
            for(int j=0; j<n; j++){
                if(i-1 != j && computers[i-1][j]==1){
                    adjacent[i].add(j+1);
                    adjacent[j+1].add(i);
                }
            }
        }
        
        for(int i=1; i<=n; i++){
            if(!visited[i]){
                bfs(i, adjacent);
            }
        }
        
        return answer=cnt;
    }
}