BOJ02606 바이러스

https://www.acmicpc.net/problem/2606 (opens new window)

신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.

제출 코드

연결 리스트를 활용하여 그래프를 양방향으로 세팅한다.

for (int i = 0; i < edgeCount; i++) {
    int a = scanner.nextInt();
    int b = scanner.nextInt();

    graph.get(a).add(b);
    graph.get(b).add(a);
}

1번 컴퓨터 부터 시작하기 때문에 1번 node를 기준으로 너비 우선 탐색을 진행한다.

private static int bfs(int node) {
    int count = 0;
    Queue<Integer> queue = new LinkedList<>();
    queue.add(node);
    visited[node] = true;

    while (!queue.isEmpty()) {
        node = queue.poll();
        List<Integer> nodes = graph.get(node);
        for (Integer value : nodes) {
            if (!visited[value]) {
                visited[value] = true;
                count++;
                queue.add(value);
            }
        }
    }

    return count;
}

아래는 최종 제출 코드이다.

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

public class BOJ2606 {

    static List<List<Integer>> graph = new ArrayList<>();
    static boolean[] visited;

    private static int bfs(int node) {
        int count = 0;
        Queue<Integer> queue = new LinkedList<>();
        queue.add(node);
        visited[node] = true;

        while (!queue.isEmpty()) {
            node = queue.poll();
            List<Integer> nodes = graph.get(node);
            for (Integer value : nodes) {
                if (!visited[value]) {
                    visited[value] = true;
                    count++;
                    queue.add(value);
                }
            }
        }

        return count;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int nodeCount = scanner.nextInt();
        int edgeCount = scanner.nextInt();

        visited = new boolean[nodeCount + 1];
        for (int i = 0; i <= nodeCount; i++) {
            graph.add(new ArrayList<>());
        }

        for (int i = 0; i < edgeCount; i++) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();

            graph.get(a).add(b);
            graph.get(b).add(a);
        }

        System.out.println(bfs(1));
    }
}

#algorithm #BOJ #그래프 이론 #그래프 탐색 #너비 우선 탐색 #깊이 우선 탐색