P43162. 네트워크

문제

제출 코드

• 사용 알고리즘 : BFS

주어진 노드들이 연결된 네트워크 집합의 개수를 세는 union-find 문제인데, BFS나 DFS로도 간단하게 풀릴 수 있을거 같아서 BFS로 풀었다.

간선 정보까지 인접배열로 주어져있어서, 입력값을 어떻게 저장할 지 고려할 필요가 없어 더욱 쉬웠던 문제.

import java.util.*;

class Solution {
    public int solution(int n, int[][] computers) {
        int answer = 0;
        boolean[] visit = new boolean[n];

        for(int i=0; i<n; i++){
            if(visit[i]) continue;

            answer++;
            visit[i] = true;

            Queue<Integer> queue = new LinkedList<Integer>();
            queue.add(i);

            while(!queue.isEmpty()){
                int now = queue.poll();
                for(int j=0; j<n; j++){
                    if(!visit[j] && computers[now][j]==1) {
                        visit[j] = true;
                        queue.add(j);
                    }
                }
            }
        }
        return answer;
    }
}