99클럽 코테 스터디 15일차 TIL - 프로그래머스 '네트워크'

항해99 코테 스터디 15일차 문제인 프로그래머스의 '네트워크'는 노드와 엣지로 구성된 컴퓨터 네트워크 그래프에서, 연결된 네트워크의 개수를 구하는 문제다. 난이도는 레벨3이며 DFS/BFS를 통해 해결할 수 있다.

 

오늘의 문제 - 네트워크 문제 정보

문제 키워드

- DFS/BFS

난이도

- Level 3

 

문제 요약

• 전체 컴퓨터의 개수 n과, 각 컴퓨터간의 연결 정보 행렬 computers가 주어진다.
• 서로 연결되어있는 컴퓨터 그룹을 하나의 네트워크라고 할 때, 몇개의 네트워크가 존재하는지를 구하여라.

 

문제 풀이 과정  

• DFS 또는 BFS를 사용하면 한 노드와 연결된 다른 노드들을 확인할 수 있다는 점을 이용하였다.
• 아직 방문하지 않은 노드에서부터 BFS를 수행하여 연결된 노드들을 방문 표시하며, 네트워크의 개수를 구했다.

코드

import java.util.*;

class Solution {
    
    private boolean[] visited;
    
    public int solution(int n, int[][] computers) {
        int answer = 0;
        visited = new boolean[n];
        
        for(int i=0; i<n; i++) {
            if(!visited[i]) {
                answer++;
                bfs(i, computers);
            }
        }
        
        return answer;
    }
    
    private void bfs(int start, int[][] adjs) {
        Queue<Integer> q = new LinkedList<>();
        q.add(start);
        visited[start] = true;
        
        while(!q.isEmpty()) {
            int here = q.poll();
            
            for(int next=0; next<adjs.length; next++) {
                if (adjs[here][next]==1 && !visited[next]) {
                    visited[next] = true;
                    q.add(next);
                }
            }
        }
    }
}

• 시간복잡도: O(N)
• 공간복잡도: O(N)