[BOJ] 2606 바이러스 - Java

[문제]

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

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

어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.

 

[문제 풀이]

이 문제는 BFS 또는 DFS를 이용하여 해결 할 수 있다.

그리고 BFS와 DFS를 구현하는데 matrix 또는 list로 구현이 가능한데 두 가지 방법으로 다 풀어보았다.

 

1. BFS Linked list

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int N, M;
    static Queue<Integer> q = new LinkedList<>();
    static boolean[] visited;
    static Node[] adj;

    static int stoi(String s) {
        return Integer.parseInt(s);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = stoi(br.readLine());
        M = stoi(br.readLine());

        visited = new boolean[N+1];
        adj = new Node[N+1];

        for (int i=0; i<M; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int u = stoi(st.nextToken());
            int v = stoi(st.nextToken());

            adj[u] = new Node(v, adj[u]);
            adj[v] = new Node(u, adj[v]);
        }

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

    public static int bfs(int n) {
        int cnt = 0;
        visited[n] = true;
        q.offer(n);

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

            for (Node node=adj[x]; node!=null; node=node.next) {
                if (!visited[node.n]) {
                    q.offer(node.n);
                    visited[node.n] = true;
                    cnt++;
                }
            }
        }

        return cnt;
    }

    static class Node {
        int n;
        Node next;

        public Node(int n, Node next) {
            this.n = n;
            this.next = next;
        }
    }
}

2. DFS Linked list

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int n, m;
    static Node[] adj;
    static boolean[] visit;
    static int cnt;

    public static int stoi(String s) {
        return Integer.parseInt(s);
    }

    public  static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = stoi(br.readLine());
        m = stoi(br.readLine());

        adj = new Node[n+1];
        visit = new boolean[n+1];
        for (int i=0; i<m; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int u = stoi(st.nextToken());
            int v = stoi(st.nextToken());

            adj[u] = new Node(v, adj[u]);
            adj[v] = new Node(u, adj[v]);
        }

        dfs(1);
        System.out.println(cnt);
    }

    public static void dfs(int v) {
        visit[v] = true;

        for (Node node=adj[v]; node!=null; node=node.next) {
            if (!visit[node.n]) {
                cnt++;
                dfs(node.n);
            }
        }
    }

    static class Node {
        int n;
        Node next;

        public Node(int n, Node next) {
            this.n = n;
            this.next = next;
        }
    }
}

3. DFS Matrix

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int n, m;
    static int[][] matrix;
    static boolean[] visit;
    static int cnt;

    public static int stoi(String s) {
        return Integer.parseInt(s);
    }

    public  static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = stoi(br.readLine());
        m = stoi(br.readLine());

        matrix = new int[n+1][n+1];
        visit = new boolean[n+1];
        for (int i=0; i<m; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int u = stoi(st.nextToken());
            int v = stoi(st.nextToken());

            matrix[u][v] = 1;
            matrix[v][u] = 1;
        }

        dfs(1);
        System.out.println(cnt);
    }

    public static void dfs(int v) {
        visit[v] = true;

        for (int i=1; i<=n; i++) {
            if (matrix[v][i]==1 && !visit[i]) {
                cnt++;
                dfs(i);
            }
        }
    }
}

[결과]

BFS - list

DFS - list

DFS - matrix

순으로 결과는 다음과 같이 나왔다.