[프로그래머스] 네트워크 - 자바

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

프로그래머스

 

1. 코드

---

DFS나 BFS를 통해서 노드간의 연결을 탐색하는 문제이다. 연결 요소의 개수를 찾는 것과 똑같다.

 

각 노드마다 DFS를 돌려서 연결 요소의 개수를 카운팅 하면 되는 문제이다.

 

백준에서 11724 ( 연결요소의 개수 )와 비슷한 문제이다.

 

2. 코드

---

class Solution {
    static boolean[] visited; // 방문 체크용
	static int answer = 0;
	
	public int solution(int n, int[][] computers) {
        visited = new boolean[n];
        
        // 각 노드별로 dfs탐색
        for(int i = 0; i < n; i++) {
        	if(visited[i] != true) {
        		answer++; // 새로운 연결요소를 찾을때마다 카운팅.
        		dfs(i, n, computers);
        	}
        }
        
        return answer;
    }
	
	public void dfs(int idx, int n, int[][] computer) {
		if(visited[idx] == true)
			return;
		visited[idx] = true;
		for(int i = 0; i < n; i++) {
			if(computer[idx][i] == 1 && visited[i] != true) {
				dfs(i, n, computer);
			}
		}
	}
}