1. 문제 설명
서로 연결되어 있는 그래프를 하나의 군집체로 볼 때, 주어진 전체 노드에서 군집체가 총 몇 개 있는지 구하는 문제이다.
2. 접근 방식
- 인접 리스트 형태로, 노드와 연결 정보를 저장한다.
- 방문 배열을 만들고 방문하지 않은 배열을 기점으로 BFS를 실행한다.
한 번 BFS를 돌면, 시작 정점과 연결된 모든 정점은 방문 처리가 될 것이다. 이는 하나의 군집체를 조회한 걸로 볼 수 있다. - 따라서 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);
}
}
}
}
}
0