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

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

 

프로그래머스

---

문제 분석

 

 

• 네트워크란 컴퓨터 간에 정보를 교환할 수 있는 형태를 의미 (즉, 한개씩이라도 연결되있는 상태)
• 컴퓨터 개수와 연결정보를 가지고 네트워크가 몇 개인지 출력

 

해결 키 포인트

• BFS 이용

---

코드

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public static boolean [] visited;
    public static ArrayList[] lists;
    public static int count = 0;

    public int solution(int n, int[][] computers) {
        visited = new boolean[n];
        lists = new ArrayList[n];
        for(int i=0;i<n;i++) {
            lists[i] = new ArrayList<>();
            for(int j=0;j<computers[i].length;j++) {
                if(j!=i && computers[i][j] == 1) {
                    lists[i].add(j);
                }
            }
        }

        for(int i=0;i<n;i++) {
            BFS(i);
        }
        
        return count;
    }

    public void BFS(int index) {
        Queue<Integer> queue = new LinkedList<>();
        
        if(!visited[index]) {
            visited[index] = true;
            queue.add(index);
            while (!queue.isEmpty()) {
                int queueSize = queue.size();
                for (int i = 0; i < queueSize; i++) {
                    int newIndex = queue.poll();

                    ArrayList<Integer> list = lists[newIndex];

                    for (int j = 0; j < list.size(); j++) {
                        int n = list.get(j);
                        if (!visited[n]) {
                            visited[n] = true;
                            queue.add(n);
                        }
                    }
                }
            }
            count++;
        }
    }
}