[프로그래머스] 네트워크

1. 문제

---

프로그래머스

2. 풀이 과정

---

0. 초기 상태

 

1. 0부터 깊이 우선 탐색을 통해 컴퓨터들을 방문한다.

• 깊이 우선 탐색이 끝나면 네트워크 개수를 하나 증가시킨다. --> 1

 

2. 방문하지 않은 노드를 시작 노드로 하여 다시 깊이 우선 탐색을 한다.

• 깊이 우선 탐색이 끝나면 네트워크 개수를 하나 증가시킨다. --> 2

3. 방문하지 않은 노드가 없을 때까지 반복한다.

• 모든 노드를 방문했으므로 끝

네트워크 개수: 2

3. 내 코드

---

import java.util.*;
class Solution {
    public int solution(int n, int[][] computers) {
        
        boolean[] visited = new boolean[n];
        int network_cnt = 0;
        
        
        for(int i = 0; i < n; i++) {
            if(!visited[i]){
                // 아직 방문하지 않은 노드를 시작 노드로 해서 DFS하기
                dfs(i, visited, computers);
                // 네트워크 개수 하나 추가
                network_cnt++;
            }
        }

        
        return network_cnt;
    }
    
    private static void dfs(int cur_node, boolean[] visited, int[][] computers) {
        
        Stack<Integer> stack = new Stack<>();
        
        stack.push(cur_node); // 시작 노드 스택에 넣기
        while(!stack.isEmpty()){
            cur_node = stack.pop(); // 스택에서 꺼내기
            visited[cur_node] = true; // 해당 노드 방문처리

            int[] graph = computers[cur_node];


            for(int i = 0; i < graph.length; i++) {
                if(!visited[i] && graph[i] == 1) 
                    stack.push(i);
            }
        }
    }
}

시간 복잡도

• O(N^2)

N개의 노드를 방문하는데 각각 인접한 노드를 찾을 때 N*N크기의 인접행렬을 참조하므로 O(N^2)

4. 피드백

---

• 모든 노드를 탐색할 때는 깊이 우선 탐색이 더 효율적이다.