[DFS] 프로그래머스 - 네트워크 문제 Java 풀이

[공부용이기 때문에 코드가 깔끔하지 않을 수 있습니다!]

 

프로그래머스

문제는 다음과 같다.

입출력 예

 

네트워크 개수

예를 들어 [[1, 1, 0], [1, 1, 1], [0, 1, 1]]으로 이루어진 컴퓨터들이 있으면 자신의 컴퓨터 외에 다른 컴퓨터와 간선으로 이루어져 네트워크를 구성하는데 이때 네트워크 그룹의 위의 사진과 같이 세는 문제였다.

코드

class Solution {
    int[][] coms;
    static boolean[] check;
    int n;

    public boolean[] dfs(int x){
        check[x] = true;

        for (int i = 0; i < n; i++) {
            if (i != x && coms[x][i] == 1 && !check[i]) {
                check = dfs(i);
            }
        }

        return check;
    }

    public int solution(int temp, int[][] computers) {
        int answer = 0;
        n = temp;
        check = new boolean[n];
        coms = computers;

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

        return answer;
    }
}

위 코드를 보면 흐름은

1. 루트 노드(0번째 배열)부터 시작하면서 자신과 연결되어 있는 노드들을 방문하여 체크 처리를 해준다. (이때 카운트 +1)
2. 그러면 연결되어있지 않은 노드들을 DFS를 돌려 연결되어있는 노드를 찾는다.(이때도 카운팅)

2번 과정이 반복되면 마지막에 네트워크 개수가 나온다.

어렵다 어려워...