// GRAPH TRAVERSAL · BFS

BFS로
네트워크 개수 세기

인접 행렬을 인접 리스트로 바꾸는 과정부터, `visited` 배열이 왜 필요한지, BFS가 연결 요소를 어떻게 한 번에 방문하는지까지 네트워크 문제 기준으로 정리한 노트입니다.

BFS 원리

BFS는 시작 정점에서 가까운 정점부터 차례대로 방문하는 그래프 순회 방식입니다. 이 문제에서는 하나의 컴퓨터에서 출발해 연결된 모든 컴퓨터를 한 번에 방문하는 데 사용합니다.

핵심 역할

시작 정점과 같은 네트워크에 속한 정점을 전부 방문 처리합니다.

이 문제에서의 의미

BFS 한 번이 곧 연결 요소 하나, 즉 네트워크 하나를 찾는 과정입니다.

      문제의 본질

      바깥 반복문으로 모든 정점을 확인하면서, 아직 방문되지 않은 정점에서만 BFS를 시작합니다.

      이때 BFS 호출 횟수가 곧 정답인 네트워크 개수가 됩니다.

visited 배열이 필요한 이유

`visited`가 없으면 같은 정점을 여러 번 큐에 넣게 되고, 이미 확인한 네트워크를 다시 탐색하게 됩니다. 이 문제에서는 중복 방문을 막는 것뿐 아니라, 이미 세어본 네트워크를 또 세지 않기 위해서도 꼭 필요합니다.

BFS 내부

인접 정점을 볼 때 이미 방문했다면 다시 큐에 넣지 않습니다.

바깥 반복문

이미 방문된 시작점에서는 BFS를 다시 호출하지 않으므로 네트워크를 중복 계산하지 않습니다.

      정리

      `visited`는 "이 정점을 이미 처리했는가?"를 기록합니다.

      BFS 안에서는 중복 방문 방지, BFS 밖에서는 연결 요소 중복 카운트 방지 역할을 합니다.

인접 행렬을 그래프로 만들기

입력은 `computers[i][j]` 형태의 인접 행렬입니다. BFS는 인접 정점을 빠르게 순회해야 하므로, 먼저 이를 인접 리스트 `graph`로 변환합니다.

      // graph 만들기
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) {
    graph.add(new ArrayList<>());
}

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        if (i == j) continue;
        if (computers[i][j] == 1) {
            graph.get(i).add(j);
        }
    }
}

예제 1: `[[1,1,0],[1,1,0],[0,0,1]]` 에서 graph 만들기

0. 초기화

1. 0행 처리

2. 1행 처리

3. 자기 자신 건너뛰기

4. 완료

ADJACENCY LIST

문제 해설

이 풀이의 흐름은 단순합니다. 그래프를 만든 뒤, 모든 정점을 순회하면서 아직 방문되지 않은 정점에서만 BFS를 시작합니다.

1. 그래프 생성

인접 행렬을 인접 리스트로 바꿔 BFS가 인접 정점을 순회하기 쉽게 만듭니다.

2. 전체 순회

0번부터 n-1번까지 보면서 방문되지 않은 정점을 찾습니다.

3. BFS 실행

해당 정점과 연결된 모든 정점을 방문 처리합니다.

4. 개수 증가

BFS 한 번이 네트워크 하나이므로 `cnt++` 합니다.

      // ParkYubin.java
private void bfs(int start, boolean[] visited, List<List<Integer>> graph) {
    Queue<Integer> q = new LinkedList<>();

    q.offer(start);
    visited[start] = true;

    while (!q.isEmpty()) {
        int now = q.poll();

        for (int next : graph.get(now)) {
            if (!visited[next]) {
                visited[next] = true;
                q.offer(next);
            }
        }
    }
}

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

    // graph 생성
    List<List<Integer>> graph = new ArrayList<>();
    for (int i = 0; i < n; i++) graph.add(new ArrayList<>());

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j) continue;
            if (computers[i][j] == 1) graph.get(i).add(j);
        }
    }

    // 연결 요소 개수 세기
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            bfs(i, visited, graph);
            cnt++;
        }
    }

    return cnt;
}

      시간복잡도

      그래프 생성은 `O(N²)`이고, BFS 전체 순회도 모든 정점과 간선을 한 번씩만 보므로 이 문제 전체는 입력 형태상 `O(N²)`로 보면 됩니다.

시뮬레이션

아래 예제들은 코드가 실제로 어떤 순서로 동작하는지 보여주기 위한 단계별 시뮬레이션입니다.

예제 2: `[[1,1,0],[1,1,1],[0,1,1]]` 에서 BFS 한 번이 어떻게 퍼지는가

0. 시작 정점 삽입

1. 0 poll

2. 1 방문

3. 1 poll

4. 2 방문

5. 2 poll

6. 종료

QUEUE

VISITED

예제 1: `[[1,1,0],[1,1,0],[0,0,1]]` 에서 네트워크 수가 2가 되는 과정

0. 0번 확인

1. 첫 BFS

2. 1번 skip

3. 두 번째 BFS