99클럽 코테스터디 31일차 TIL + [프로그래머스] 네크워크 java 풀이

1. 문제 설명

문제 링크

서로 연결되어 있는 그래프를 하나의 군집체로 볼 때, 주어진 전체 노드에서 군집체가 총 몇 개 있는지 구하는 문제이다.

2. 접근 방식

1. 인접 리스트 형태로, 노드와 연결 정보를 저장한다.
2. 방문 배열을 만들고 방문하지 않은 배열을 기점으로 BFS를 실행한다.
   한 번 BFS를 돌면, 시작 정점과 연결된 모든 정점은 방문 처리가 될 것이다. 이는 하나의 군집체를 조회한 걸로 볼 수 있다.
3. 따라서 BFS를 돈 횟수만큼 군집체가 존재하는 것이므로, BFS를 실행한 횟수를 반환하면 된다.

3. 코드 분석

import java.io.*;
import java.util.*;

class Solution {
    public int solution(int n, int[][] computers) {
        int answer = 0;
        ArrayList<Integer> [] lists = new ArrayList [n];
        boolean [] isVisited = new boolean [n];

        for(int i = 0; i < n; i++){
            lists[i] = new ArrayList<>();
            for(int j = 0; j < n; j++){
                if(computers[i][j] == 1){
                    if(i==j) continue;
                    lists[i].add(j);
                }
            }
        }

        for(int i = 0; i < n; i++){
            if(!isVisited[i]){
                answer++;
                bfs(lists,isVisited, i);
            }
        }

        return answer;
    }

    public void bfs(ArrayList<Integer> [] lists, boolean [] isVisited, int node) {
        ArrayDeque<Integer> aq1 = new ArrayDeque<>();
        aq1.add(node);
        isVisited[node] = true;

        while(!aq1.isEmpty()){
            int now = aq1.poll();
            for(int i = 0; i < lists[now].size(); i++){
                int next = lists[now].get(i);
                if(!isVisited[next]){
                    isVisited[next] = true;
                    aq1.add(next);
                }
            }
        }
    }
}