문제

프로그래머스 - 네트워크

요약

총 노드 개수가 n으로 주어지고, 노드들의 연결된 정보가 2차원 배열로 주어질 때, 연결될 수 있는 네트워크 집합들의 총 개수를 구해야한다!

접근

0번 노드부터 접근하면서 깊이 우선 탐색(DFS)를 돌리면서 방문한 노드들을 visited로 처리하면서 연결하면 되겠다!라는 생각을 가지고 접근

알고리즘

1. 주어지는 n과 computers 배열을 클래스변수로 빼고, 네트워크 개수를 저장할 변수도 클래스 변수로 지정한다.
2. visited 배열을 생성해 노드 방문 여부를 저장한다.
3. 0번 노드부터 차례로 방문하면서 방문한 node들을 visited = true로 저장한다.
4. 각 노드와 연결된 노드들을 다 방문할때까지 visited 여부를 확인하고 업데이트하는 것을 반복한다.

최종 코드

class Solution {
    int n;
    int[][] computers;
    int answer;
    boolean[] visited;
    
    public int solution(int n, int[][] computers) {
        this.n = n;
        this.computers = computers;
        
        visited = new boolean[n];
        
        for (int i = 0; i < n; i++) {
            findNetwork(i, i);   
        }
        
        return answer;
    }
    
    public void findNetwork(int startNode, int node) {
        if (visited[node]) return;
        
        visited[node] = true;
        
        for (int i = 0; i < n; i++) {
            // 아직 방문하지 않았으면서 연결된 노드가 있는지 확인
            if (!visited[i] && computers[node][i] == 1) findNetwork(startNode, i);
        }
        
        if (startNode == node) {
            answer++;
        }
    }
}

어려웠던 점

visited 처리는 알겠는데, 언제 네트워크 개수를 증가시켜야할지 판단하는게 어려웠다. DFS 내부에서 answer 카운트를 올리면 재귀를 돌때마다 카운트가 될 것이기에 어떻게 해야할지 고민하다, 처음 시작 노드 정보를 재귀 함수의 input으로 넣고, 연결된 노드 탐색을 모두 끝낸 후 answer를 증가시키는 방식을 택했다.
그런데, 이 코드는 짠 내가 나중에 다시봐도 이해하기 어려운데, 다른 사람이 보면 더 이해하기 어려울 것 같고, for문이 2중으로 들어간다는 측면에서 다시 최적화된 코드를 짜야겠다는 생각이 들었다.
코드가 복잡해 보이는 이유는 answer가 증가되는 방식 때문이라는 생각이 든다. 그래서 아래와 같이 코드를 재구성했다.

최적화 코드

class Solution {
    ...
    
    public int solution(int n, int[][] computers) {
        ...
        
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
            	// 최초로 노드를 탐색하기 시작할 때, 부모 노드로 삼고 네트워크 개수를 1 증가시킨다.
                answer++;
                findNetwork(i);   
            }
        }
        
        return answer;
    }
    
    // 재귀 함수 인자를 node만 받도록 수정
    public void findNetwork(int node) {
        ...
    }
}