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

박원준·2025년 11월 24일

네트워크 (Level 3)

문제설명

네트워크란 컴퓨터 간 정보 교환이 가능하도록 연결된 형태를 의미한다.
n대의 컴퓨터와 연결 정보가 인접 행렬 형태로 주어질 때,
총 몇 개의 네트워크(연결 요소)가 존재하는지 구하는 문제.

computers[i][j] = 1 → i번과 j번 컴퓨터가 직접 연결됨
직접 연결뿐 아니라 경로를 통해 간접 연결되어도 같은 네트워크

입력	설명
n	컴퓨터의 개수 (1 ≤ n ≤ 200)
computers	인접 행렬 (0/1)

✍ 풀이

🔍 문제 해석

컴퓨터는 그래프의 노드
연결 관계는 간선
computers는 인접 행렬
즉, 그래프에서 연결 요소 개수를 구하는 문제

🚀 풀이 방식 1 — BFS

인접 행렬을 기반으로 BFS로 연결된 컴퓨터들을 모두 방문하며
BFS가 시작된 횟수 = 네트워크 개수

🔑 핵심 로직

방문 배열 visited[] 생성
0번부터 n-1까지 순회하며 방문하지 않은 컴퓨터를 발견하면
- 그 컴퓨터에서 BFS 실행
- BFS 한 번 = 네트워크 1개
모든 노드를 확인하면 네트워크 개수 완료

💡 코드

import java.util.*;

class Solution {
    
    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, n, computers);
            }
        }
        
        return answer;
    }
    
    public void bfs(int v, int size, int[][] map) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(v);
        
        while(!q.isEmpty()) {
            int cur = q.poll();
            visited[cur] = true;
            
            for(int i = 0; i<size; i++){
                if(map[cur][i] == 1 && !visited[i]){
                    q.offer(i);
                }
            }
        }
    }
}

⚡ 풀이 방식 2 — Union-Find (Disjoint Set)

연결된 컴퓨터들을 하나의 집합으로 합치는 방식

🔑 핵심 로직

각 컴퓨터는 처음에 자기 자신만 소속
computers[i][j] == 1이면 union(i, j)
모든 union 처리 후
- 대표 부모(root)가 서로 다른 개수 = 네트워크 개수

💻 코드

import java.util.*;

class Solution {
    
    int[] parents;
    HashSet<Integer> set = new HashSet<>();
    
    public int find(int a) {
        if(parents[a] == a) return a;
        return parents[a] = find(parents[a]);
    }
    
    public boolean union(int a, int b) {
        int aRoot = find(a);
        int bRoot = find(b);
        
        if(aRoot == bRoot) return false;
        
        parents[bRoot] = aRoot;
        return true;
    }
    
    public int solution(int n, int[][] computers) {
        
        parents = new int[n];
        for(int i = 0; i<n; i++){
            parents[i] = i;
        }
        
        for(int i = 0; i<n; i++) {
            for(int j = 0; j<n; j++) {
                if(i==j) continue;
                
                if(computers[i][j] == 1){
                    union(i, j);
                }
            }
        }
        
        for(int i = 0; i<n; i++) {
            set.add(find(i));
        }
        
        return set.size();
    }
}