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

프로그래머스 네트워크 

https://school.programmers.co.kr/learn/courses/30/lessons/43162?language=java 

프로그래머스

아이디어

• DFS를 통해서 하나의 컴퓨터와 다른 컴퓨터가 네트워크에 연결 되어있는지 확인한다
• 같은 컴퓨터를 두번 방문하는 것을 피하기 위해서 방문 배열 visited[] 를 만들어서 체크한다
• 방문 배열을 돌면서 방문하지 않은 컴퓨터에 대해서 DFS를 수행한다
• DFS 함수 안에서는 해당 컴퓨터를 방문 처리하고, 그 컴퓨터가 방문되지 않고, 연결 되어있는지 확인한 이후
  다른 컴퓨터와 연결 되어있는지 확인하기 위해서 DFS를 수행한다

코드

class Solution {
    public static boolean[] visited;
    public static int count = 0;
    
    public int solution(int n, int[][] computers) {
        visited = new boolean[n];
        
        for (int i=0; i<computers.length; i++) {
            if (!visited[i]) {
                dfs(i, computers); // 방문하지 않은 컴퓨터면 DFS 수행하여 다른 연결 컴퓨터 확인
                count++; 
            }
        }
        
        return count;
    }
    
    public static void dfs(int start, int[][] computers) {
        visited[start] = true; // 방문처리
        
        for (int i=0; i<computers.length; i++) {
            if (!visited[i] && computers[start][i] == 1) { // 방문하지 않고 computer가 서로 연결 되어있음(==1)
                visited[i] = true;
                dfs(i, computers);
            } 
        }
    }
}