프로그래머스 Level 3 – 네트워크(Java, BFS)

🌐 프로그래머스 Level 3 – 네트워크(Java, BFS)

이번에 풀어본 문제는 프로그래머스의 대표적인 그래프 탐색 문제인 **“네트워크”**다.
회사 컴퓨터들이 서로 연결되어 있을 때, 총 몇 개의 네트워크(= 연결된 그룹)이 존재하는지 찾는 문제다.

문제 구조가 전형적인 그래프의 연결 요소 개수 찾기(Connected Components) 라서
DFS 또는 BFS 아무거나 사용해도 되지만, 나는 BFS 버전으로 풀었다.

---

📌 문제 요약

• 컴퓨터 개수: n
• 연결 관계: computers[i][j] == 1이면 i와 j는 연결됨
• 서로 이어진 컴퓨터끼리는 하나의 네트워크
• 네트워크가 총 몇 개인지 반환하는 문제

즉,

방문하지 않은 노드 하나를 발견 → 그 노드를 기준으로 BFS/DFS 돌림 → 연결된 모든 노드를 방문 처리 → 네트워크 개수 +1

이 과정이 반복된다.

---

🧠 핵심 아이디어

✔ 1. visited[] 배열로 방문 여부 체크

이미 방문한 컴퓨터는 다시 탐색하지 않는다.

✔ 2. BFS로 연결된 노드를 모두 탐색

큐를 사용해서 같은 네트워크에 속한 노드를 한 번에 방문 처리한다.

✔ 3. 외부 루프에서 방문하지 않은 노드 발견 → 네트워크 1개 추가

이 노드를 기준으로 BFS 한 번 돌리면 해당 네트워크 전체가 탐색된다.

---

🧩 자바 코드(BFS 사용)

 

import java.util.*;

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

 

---

🔍 코드 풀이 요약

✔ solution()

• 방문하지 않은 컴퓨터 i 발견 → BFS 실행
• BFS 한 번 실행할 때마다 하나의 네트워크가 완성되므로 answer++

✔ bfs()

• 큐 기반 BFS
• 현재 컴퓨터와 연결된 모든 노드를 탐색
• 방문한 컴퓨터는 vist[]로 체크

---

🧮 시간 복잡도

• BFS 전체: O(n²)
• n 최대 200이라 충분히 빠르다.

---

🎯 최종 정리

이 문제는 BFS/DFS로 푸는 그래프 입문 문제에 가깝다.
핵심은 단 하나,

방문하지 않은 노드를 하나 발견할 때마다 네트워크가 1개 늘어난다.

그래프의 기본 개념인 연결 요소(Connected Components)를 잘 이해하면 매우 쉽게 접근할 수 있다.