[ 알고리즘 ] 코딩 - Programmers - 네트워크.java

---

문제 링크

programmers.co.kr/learn/courses/30/lessons/43162

코딩테스트 연습 - 네트워크

---

* 프로그래머스 - Level3 - (자바)네트워크 - Queue를 이용한 BFS

입출력예시

---

< 로직 >

* 연결된 Vertex들은 하나의 네트워크로 보기 때문에 시작하는 Vertex에서 

* 연결된 모든 Vertex는 BFS를 순회하며 방문을 체크한다.

* 어디에도 연결이 되지 않은 독자적 Vertex는 따로 더해준다.

* 방문체크와 BFS를 이용하여 구현!

---

import java.util.LinkedList;
import java.util.Queue;
class Solution {
    public int solution(int n, int[][] computers) {
            boolean[] visited = new boolean[n]; // 방문체크 배열
	    	int answer = 0;
	    	
	    	for(int i = 0; i < n; i++) {
	    		boolean noNet = true; // 연결안된 독자적 Vertex 관리
	    		if(visited[i]) continue; // 이미 방문한 Vertex 갈 필요 없음
	    		visited[i] = true;
	    		for(int j = 0; j < n; j++) {
	    	    	if(computers[i][j] == 0) continue;
	    	    	if(visited[j]) continue;
	    	    	
                    // Vertex가 어딘가에 연결이 되어 있는 경우 BFS로 순회하며 Vertex 체크
	    	    	Queue<Integer> queue = new LinkedList<Integer>();
	    	    	queue.offer(j);
	    	    	visited[j] = true;
	    	    	
	    	    	while(!queue.isEmpty()) {
	    	    		int startVertex = queue.poll();
	    	    		
	    	    		for(int des = 0; des < n; des++) {
	    	    			if(visited[des]) continue;
	    	    			if(computers[startVertex][des] == 1) {
	    	    				queue.offer(des); // 연결된 모든 Vertex 방문
	    	    				visited[des] = true; 
	    	    			}
	    	    		}
	    	    	}
	    	    	noNet = false;
	    	    	answer++;
	    		}
	    		
                // Vertex가 어디에도 연결이 안 된 경우. 독자적 네트워크
	    		if(noNet) answer++;
	    	}
	    	
	    	
	        return answer;
    }
}