[Programmers] 네트워크 DFS 풀이 (Java)

네트워크

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

DFS 풀이

문제 설명이 길지만, 축약하자면 undirected graph 에서 연결 되지 않은 그룹이 몇개 있는지에 대한 문제다. DFS 로 그래프를 따라 가되, 이미 방문 했던 노드면 패스하고 방문하지 않았던 노드면 다시 계속 따라가게 구현하면 된다.

 

노드의 방문에 대한 여부는 미방문(0), 누군가가 방문 하고 있는 중 (1), 방문 완료(2) 로 확인할 수 있지만... 문제에선 사실 여기까진 필요없고 단순히 boolean 으로 확인하면 된다. (만약 directed graph 라면 이 알고리즘을 써야 한다. 참고)

class Solution {

    public int dfs(int i, int[][] computers, boolean[] visited) {

        if (visited[i]) {
            return 0;
        }

        visited[i] = true;
        for (int j = 0; j < computers[i].length; j++) {
            if (computers[i][j] == 1) {
                dfs(j, computers, visited);
            }
        }

        return 1;
    }

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

        return answer;
    }
}