백준 2606: BFS로 바이러스가 퍼지는 컴퓨터 세기

백준 2606번: 바이러스는 1번 컴퓨터와 연결된 컴퓨터를 찾는 문제입니다. 당시에는 입력 범위가 작아 인접 행렬로 풀었습니다.

시작 컴퓨터는 개수에서 뺍니다

1번을 큐에 넣고 방문 표시를 한 상태에서 시작합니다. 큐에서 꺼낸 컴퓨터와 연결되어 있고 아직 방문하지 않은 컴퓨터만 새로 넣습니다. 이때 count를 늘리므로 시작점인 1번은 답에 포함되지 않습니다.

큐가 빌 때까지 반복하면 1번에서 도달할 수 있는 컴퓨터를 모두 세게 됩니다.

풀이 코드와 행렬 확인용 출력

인접 행렬을 확인하려고 아래 코드에 출력문도 넣어 두었습니다. 정답 외의 내용까지 출력하므로 실제로 제출할 때는 이 확인용 반복문을 제거해야 합니다. 반복문의 범위도 N이 아니라 M + 1입니다. 그래서 보통 입력에서는 일부만 출력하거나 배열 범위를 벗어날 수 있습니다.

Java

import java.io.*;
import java.util.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());

        int[][] arr = new int[N+1][N+1];
        boolean[] visited = new boolean[N+1];

        Queue<Integer> q = new LinkedList<>();

        for (int i = 0; i < M; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            arr[a][b] = arr[b][a] = 1;
        }

        int start = 1;
        int count = 0;
        q.add(start);
        visited[start] = true;

        while (!q.isEmpty()) {
            start = q.poll();

            for (int i = 1; i < N+1; i++) {
                if (arr[start][i] == 1 && !visited[i]) {
                    q.add(i);
                    visited[i] = true;
                    count++;
                }
            }
        }
        for (int i = 1; i <= M+1; i++) {
            for (int j = 1; j <= M+1; j++) {
                bw.write(arr[i][j] + " ");
            }
            bw.flush();
            bw.newLine();
        }
        bw.write(String.valueOf(count));
        bw.flush();
    }
}

입력과 인접 행렬

인접 행렬의 모양은 다음 입력으로 확인했습니다. 컴퓨터가 7대이고 간선이 6개라 확인용 반복문의 M + 1 범위가 우연히 컴퓨터 수와 맞는 경우입니다.

이 입력을 인접 행렬로 저장하면 다음과 같습니다. 행과 열은 각각 컴퓨터 번호이고 1은 두 컴퓨터가 연결되어 있다는 뜻입니다.

0 1 0 0 1 0 0 
1 0 1 0 1 0 0 
0 1 0 0 0 0 0 
0 0 0 0 0 0 1 
1 1 0 0 0 1 0 
0 0 0 0 1 0 0 
0 0 0 1 0 0 0

이 문제는 인접 행렬로 풀었지만 다음 문제부터는 인접 리스트 방식도 사용해 보기로 했습니다.