4-9: 웜바이러스

웜바이러스 (virus.cpp)

 

문제

---

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

예를 들어 7대의 컴퓨터가 < 그림 1 > 과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크 상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.

 

입력

---

첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.

 

출력

---

1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.

 

예제 입력

7
6
1 2
2 3
1 5
5 2
5 6
4 7

예제 출력

4

import java.util.*;

public class virus {

    /**
     *
     * 문제: 신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.
     *
     *
     * 입력: 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번부터 차례대로 번호가 매겨진다.
     * 둘째 줄에는 네트워크상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.
     *
     *
     * 출력:
     * 1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.
     *
     * 예제 입력:
     * 7
     * 6
     * 1 2
     * 2 3
     * 1 5
     * 5 2
     * 5 6
     * 4 7
     *
     * 예제 출력:
     * 4
     *
     * @param args
     */

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int numConnections = sc.nextInt();

        //init n nodes
        Graph graph = new Graph();

        for (int i=0; i<N; i++){
            Node node = new Node(i+1);
            graph.addNode(node);
        }

        //add edges
        for (int i=0; i<numConnections; i++){
            int a = sc.nextInt();
            int b = sc.nextInt();
            //get node
            Node start = graph.nodeList.get(a-1);
            Node end  = graph.nodeList.get(b-1);
            graph.addEdge(start, end);
            graph.addEdge(end, start);
        }

        //traverse graph.
        Node start = graph.head;
        Queue<Node> queue = new LinkedList<>();
        queue.add(start);

        int infectionCount = 0;

        while (!queue.isEmpty()){
            Node temp = queue.remove();
            if (temp == null) break;
            if (!temp.visited){
                infectionCount ++;
//                System.out.println("infected: " + temp.data);
            }
            temp.visited = true;
            //get temp's edges, and enqueue

            if (null != graph.edgeMap.get(temp)){
                for (Edge e : graph.edgeMap.get(temp)){
                    if (!e.getEnd().visited){
                        queue.add(e.getEnd());
                    }
                }
            }

        }

        System.out.println(infectionCount-1); // exclude 1.


    }

    private static class Graph {
        Node head;
        ArrayList<Node> nodeList;
        HashMap<Node, ArrayList<Edge>> edgeMap;
        public Graph(){
            nodeList = new ArrayList<>();
            edgeMap = new HashMap<>();
        }

        public void addNode(Node a){
            nodeList.add(a);
            if (a.data == 1){
                head = a;
            }
        }

        public void addEdge(Node a, Node b){
            ArrayList<Edge> list;
            if (edgeMap.get(a)==null){
                list = new ArrayList<>();
            } else {
                list = edgeMap.get(a);
            }
            list.add(new Edge(a,b));
            edgeMap.put(a, list);
        }
    }

    private static class Node {
        int data;
        boolean visited;
        public Node(int data){
            this.data = data;
            this.visited = false;
        }
    }

    private static class Edge {
        Node a;
        Node b;
        public Edge(Node a, Node b){
            this.a = a;
            this.b = b;
        }

        public Node getEnd(){
            return b;
        }
    }
}