네트워크 - BFS

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/43162

프로그래머스

 

 

 

풀이 - 나의 생각

방문을 하면서

 

시작점을 기록합니다.

 

ex. A에서 시작해서 도착한 곳은 다 A로 저장

 

그 후에 Set으로 저장된 시작점의 개수를

 

중복없이 세면

 

네트워크의 개수가 나옵니다.

 

 

코드

 

import java.util.*;

class Solution {
    public int solution(int n, int[][] computers) {
        int answer = 0;
        int[] network = new int[n];
        Queue<Integer> q = new ArrayDeque<>();
        Set<Integer> set = new HashSet<>();
        
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(computers[i][j] == 0) continue;
                if(network[j] > 0) continue;
                q.offer(j);  
            }
            
            while(!q.isEmpty()){
                int computer = q.poll();
                network[computer] = i+1;
                
                for(int j = 0; j < n; j++){
                    if(computers[computer][j] == 0) continue;
                    if(network[j] > 0) continue;
                    q.offer(j);
                }
            }
        }
        
        for(int k : network){
            set.add(k);
        }
        return set.size();
    }
}

 

 

 

 

 

 

 

다음에 또 봐요