프로그래머스 - DFS - 네트워크

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

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

public class 네트워크 {
    public static void main(String[] args) {
        네트워크 o = new 네트워크();
        System.out.println(o.solution(3, new int[][]{{1, 1, 0}, {1, 1, 0}, {0, 0, 1}}));
    }

    private boolean[] isVisit;
    private int[][] computers;
    public int solution(int n, int[][] computers) {
        int count = 0;
        isVisit = new boolean[n];
        this.computers = computers;

        for(int i=0; i<n; i++) {
            if(!isVisit[i]) {
                dfs(i);
                count++;
            }
        }

        return count;
    }

    private void dfs(int node) {
        //프로세스
        isVisit[node] = true;
        for(int i=0; i<computers[node].length; i++) {
            if(!isVisit[i] && (computers[node][i] == 1)) {
                dfs(i);
            }
        }
    }
}

알고리즘

• 완전탐색, DFS
• DFS로 순회하며 완전탐색을 한다.
• DFS한번 실행될때마다 네트워크 하나가 추가된다