[JAVA] dfs : 네트워크

1. 문제 내용

요약
n개의 컴퓨터가 있고, n개의 컴퓨터가 제각각 연결되어있을 때 총 네트워크망의 개수를 구해라

2. 접근 방법
탐색 한번에 연결되있는 모든 컴퓨터를 찾고 탐색이 되지않은 컴퓨터가 있을 때 탐색을 또 하는 방식으로 하면 될 것으로 생각되서 적합한 DFS를 사용했다

3. 구현 과정

public void dfs(int n, int[][] arr, boolean[] visible, int index){
    if(!visible[index]) {
        visible[index] = true;
        for (int i = 0; i < n; i++) {
            if(arr[index][i] == 1) dfs(n, arr, visible, i);
        }
    }
}

visible을 통해 탐색기록을 저장면서 최초탐색의 경우 연결된 컴퓨터를 다시 탐색한다

public int solution(int n, int[][] computers) {
    int count = 0;
    boolean[] visible = new boolean[computers.length];
    for(int i = 0; i < n; i++){
        if(!visible[i]){
            count++;
            dfs(n, computers, visible, i);
        }
    }

    return count;
}

탐색을 지시할 땐 방문기록을 기준으로 탐색한다

4. 결과

전체 코드

class Solution {
    public int solution(int n, int[][] computers) {
        int count = 0;
        boolean[] visible = new boolean[computers.length];
        for(int i = 0; i < n; i++){
            if(!visible[i]){
                count++;
                dfs(n, computers, visible, i);
            }
        }

        return count;
    }
    public void dfs(int n, int[][] arr, boolean[] visible, int index){
        if(!visible[index]) {
            visible[index] = true;
            for (int i = 0; i < n; i++) {
                if(arr[index][i] == 1) dfs(n, arr, visible, i);
            }
        }
    }
}