[프로그래머스] 네트워크(Lv3, BFS/DFS, 시간복잡도, Java, 정답, 코드)

programmers.co.kr/learn/courses/30/lessons/43162?language=java

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

 

 

## 접근방법

---

같은 네트워크들끼리는 무조건 연결되어 있다는 점을 착안해서 문제를 풀어보자. 어떤 컴퓨터에서 탐색을 시작하면, 연결된 컴퓨터들을 모두 찾을 수 있다. 

 

 

 

완전 탐색 기법인, BFS와 DFS를 둘다 가능하며, 시간복잡도는 O(N * N)이다. 완전 탐색 시에, 네트워크가 정해진 컴퓨터는 방문하지 않도록 체크한다.

 

 

 

생각보다 간단한 문제이므로, BFS와 DFS 코드를 통해서 이해하면 된다.

 

 

 

## BFS

---

import java.util.*;
 
class Solution {
    public int solution(int n, int[][] computers) {
        int[] network = new int[computers.length];
        int networkNum = 1;
        
        for(int i = 0; i < computers.length; i++){
            if(network[i] == 0){
                Queue<Integer> q = new LinkedList<>();
                q.add(i);
                network[i] = networkNum;
                
                while(!q.isEmpty()){
                    int cur = q.poll();
                    for(int next = 0; next < computers[cur].length; next++){
                        if(computers[cur][next] == 1 && network[next] == 0){
                            network[next] = 1;
                            q.add(next);
                        }
                    }
                }
                
                networkNum++;
            }
        }
        
        return networkNum - 1;
    }
}

 

 

 

 

## DFS

---

class Solution {
    void dfs(int cur, int networkNum, int[][] computers, int[] network){
        for(int i = 0; i < computers[cur].length; i++){
            if(computers[cur][i] == 1 && network[i] == 0){
                network[i] = networkNum;
                dfs(i, networkNum, computers, network);
            }
        }
    }
    
    public int solution(int n, int[][] computers) {
        int[] network = new int[computers.length];
        int networkNum = 1;
        
        for(int i = 0; i < computers.length; i++){
            if(network[i] == 0){
                network[i] = networkNum;
                dfs(i, networkNum, computers, network);
                networkNum++;
            }
        }
        
        return networkNum - 1;
    }
}