[프로그래머스 Lv.3] 네트워크(Java) - BFS

📌 핵심 요약

• 탐색 시작 횟수 = 정답 — BFS는 시작 노드가 속한 덩어리 전체를 방문하고 멈춘다. 따라서 BFS를 몇 번 시작했는지가 곧 네트워크 개수다.
• 방문 배열은 1차원 — 관리해야 할 상태는 "이 컴퓨터를 이미 세었는가"이므로 주어는 컴퓨터다. 간선이 아니다.
• 인접 행렬을 그대로 사용 — computers가 이미 인접 행렬이므로 별도 자료구조로 옮기지 않았다. n ≤ 200이라 O(n²)로 충분하다.

 

목차

프로그래머스 #43162

네트워크

n ≤ 200 · 깊이/너비 우선 탐색

난이도: [Level 3]

컴퓨터 n대가 있고, 어떤 두 컴퓨터가 직접 또는 간접적으로 연결되어 있으면 같은 네트워크로 본다. 연결 정보는 n×n 인접 행렬 computers로 주어진다. computers[i][j]가 1이면 i번과 j번이 연결되어 있다는 뜻이며, 자기 자신을 나타내는 computers[i][i]는 항상 1이다. 네트워크의 개수를 반환하면 된다.

풀이 과정

1. 문제를 "연결 요소 개수 세기"로 번역한다.
2. 0번부터 순서대로 훑으면서 아직 방문하지 않은 컴퓨터를 찾는다.
3. 찾을 때마다 개수를 1 올리고, 그 지점에서 BFS로 덩어리 전체를 방문 처리한다.
4. 순회가 끝나면 누적된 개수가 정답이다.

1 문제를 한 문장으로 번역했다

문제를 처음 읽었을 때 가장 먼저 한 일은 "네트워크"라는 단어를 그래프 용어로 바꾸는 것이었다.

컴퓨터는 노드이고 연결은 간선이다. 그러면 문제는 이렇게 다시 쓸 수 있다.

ℹ️

번역된 문제

노드 n개와 간선 정보가 주어졌을 때, 연결 요소(Connected Component)가 몇 개인가.

이 번역이 되는 순간 문제는 사실상 끝난다고 판단했다. 연결 요소 개수 세기는 정형화된 문제라 풀이의 틀이 이미 정해져 있기 때문이다. 

2 코드보다 규모 판단을 먼저 했다

제약 조건은 n ≤ 200이다. 이 숫자로 어떤 복잡도까지 허용되는지 먼저 계산했다.

복잡도	n = 200일 때 연산 횟수	판정
O(n²)	40,000	여유
O(n³)	8,000,000	통과 가능
O(2ⁿ)	계산 불가	탈락

O(n³)까지 허용된다는 것은 성능 최적화를 신경 쓸 필요가 전혀 없다는 뜻이다.

그러면 남는 판단 기준은 하나뿐이다. 어느 쪽이 덜 틀리는가.

💡

규모 판단을 먼저 하면 얻는 것

"미리 정리해두면 더 빠르지 않을까" 같은 최적화 유혹에 흔들리지 않게 된다. 성능이 이미 여유롭다는 결론을 코드 작성 전에 확정해두면, 이후의 모든 선택을 가독성 기준으로만 할 수 있다.

3 입력을 있는 그대로 쓰기로 했다

computers는 이미 인접 행렬이다. 그리고 탐색 중에 던져야 할 질문은 딱 하나뿐이다.

— "a와 b는 연결되어 있는가?"

인접 행렬에서 이 질문의 답은 computers[a][b] == 1, 배열 접근 한 번이다. 이미 최적이다.

그래서 이 자료구조를 다른 형태로 바꿔야 할 이유가 있는가를 스스로에게 물었다.

인접 리스트로 변환하는 것은 간선이 희소해서 매번 n칸을 훑는 비용이 아까울 때 하는 일이다. 하지만 2번에서 O(n²)이 여유롭다는 결론이 이미 나 있었으므로, 변환하지 않기로 했다. 손대지 않은 원본이 가장 안전하다고 판단했다.

4 무엇을 방문 처리할 것인가

이 문제에서 실제로 설계 판단이 필요한 지점은 여기 하나뿐이었다. 답이 "그룹의 개수"이므로, 탐색 중에 관리해야 할 상태는 다음 문장으로 정리된다.

ℹ️

관리할 상태

"이 컴퓨터는 이미 어떤 그룹에 속한 것으로 세었는가?"

문장의 주어가 컴퓨터다. 간선이 아니다. 따라서 방문 배열은 boolean[n] 1차원이면 충분하다.

답의 단위와 상태의 단위를 맞춰본다

이 판단을 굳히기 위해 사용한 확인 절차가 있다. 답의 단위와 상태의 단위가 일치하는지 대조해보는 것이다.

만약 문제가 물었다면	답의 단위	필요한 상태
네트워크 개수 (이 문제)	컴퓨터의 집합	boolean[n] — 노드 단위
끊어진 연결선의 개수	간선	boolean[n][n] — 간선 단위

답이 컴퓨터의 집합을 세는 것이므로 상태도 컴퓨터 단위여야 한다. 간선 단위 상태가 필요한 경우는 두 번째 행처럼 답 자체가 간선을 세는 문제일 때다.

5 탐색과 정답을 연결하는 구조

BFS의 성질을 한 문장으로 쓰면 다음과 같다.

— 한 노드에서 시작하면, 그 노드가 속한 덩어리 전체를 방문하고 멈춘다.

종이 위에 떨어뜨린 잉크 한 방울과 같다. 이어진 영역까지만 번지고 끊긴 곳은 넘어가지 못한다.

그러면 전체 구조는 이렇게 잡힌다.

1. 0번부터 순서대로 훑는다
2. 아직 잉크가 닿지 않은 컴퓨터를 만나면 → 새 덩어리를 발견한 것 → 개수 +1
3. 거기서 BFS를 돌려 그 덩어리를 전부 물들인다
4. 계속 훑는다

💡

BFS 시작 횟수가 곧 정답이다

개수를 세는 일은 바깥 루프의 몫이고, BFS는 "물들이기"만 담당한다. 역할이 나뉘어 있으므로 BFS 메서드는 값을 반환할 필요가 없다. void로 두었다.

6 전체 코드

   

Java — Solution.java

import java.util.*;

class Solution {
    public int solution(int n, int[][] computers) {
        boolean[] visited = new boolean[n];
        int answer = 0;

        for (int start = 0; start < n; start++) {
            // 이미 어떤 네트워크에 속한 것으로 세었다면 건너뛴다
            if (visited[start]) continue;

            // 새 네트워크를 발견한 시점
            answer++;
            bfs(start, n, computers, visited);
        }

        return answer;
    }

    private void bfs(int start, int n, int[][] computers, boolean[] visited) {
        Deque<Integer> queue = new ArrayDeque<>();
        queue.add(start);
        visited[start] = true;

        while (!queue.isEmpty()) {
            int current = queue.poll();

            for (int next = 0; next < n; next++) {
                if (computers[current][next] == 1 && !visited[next]) {
                    visited[next] = true;
                    queue.add(next);
                }
            }
        }
    }
}

대각선을 따로 걸러내지 않은 이유

computers[i][i]는 항상 1이므로 자기 자신도 조건을 통과한다. 그런데 i != j 같은 조건을 추가하지 않았다.

이유를 start = 0인 상황으로 추적해보면 다음과 같다.

시점	visited[0]	동작
BFS 진입 직후	true	visited[start] = true로 이미 표시함
current=0, next=0	true	computers[0][0] == 1은 참이지만 !visited[0]이 거짓 → 무시

방문 표시를 큐에 넣는 시점에 찍어두었기 때문에 대각선이 자동으로 걸러진다. 별도 조건이 필요 없다.

⚠️

방문 표시 위치를 옮기면 안 되는 이유

방문 표시를 큐에서 꺼낼 때(poll 직후)로 옮기면 이 보장이 깨진다. 0번이 큐에 두 번 들어가고, 일반 간선에서도 같은 노드가 중복 삽입된다. "큐에 넣을 때 방문 표시"는 BFS에서 지켜야 할 규칙이다.

동작 추적

n = 3, computers = [[1,1,0],[1,1,0],[0,0,1]]로 바깥 루프를 따라가보았다.

start	visited (진입 전)	동작	answer
0	[F, F, F]	미방문 → 카운트, BFS로 0·1 방문 처리	1
1	[T, T, F]	이미 방문 → 건너뜀	1
2	[T, T, F]	미방문 → 카운트, BFS로 2 방문 처리	2

결과 2로 예시 답과 일치한다.

복잡도

• 바깥 루프 — 노드 n개를 순회하므로 O(n)
• BFS 전체 — 각 노드는 큐에 한 번만 들어가고, 꺼낼 때마다 next를 n번 훑으므로 O(n²)

합쳐서 O(n²). n ≤ 200이므로 40,000회로 여유롭다.

7 고르지 않은 선택지

방법	코드량	판단
BFS	짧음	선택 큐 동작이 눈에 보여 추적이 쉽다
DFS (재귀)	더 짧음	동등 n=200이라 스택 깊이도 안전하다
유니온 파인드	중간	과함 간선을 다 합친 뒤 서로 다른 루트를 세는 방식. 맞지만 이 문제에는 과하다

DFS로 바꾸면 큐 없이 다음과 같이 된다.

   

Java — DFS 버전

private void dfs(int current, int n, int[][] computers, boolean[] visited) {
    visited[current] = true;

    for (int next = 0; next < n; next++) {
        if (computers[current][next] == 1 && !visited[next]) {
            dfs(next, n, computers, visited);
        }
    }
}

바깥 루프 구조는 완전히 동일하다. "탐색 시작 횟수 = 연결 요소 개수"라는 틀이 핵심이고, 그 안을 BFS로 채울지 DFS로 채울지는 부차적인 선택이다.

잘못된 내용이 있다면 지적부탁드립니다. 방문해주셔서 감사합니다.