2606번: 바이러스_DFS/BFS [JAVA]

https://www.acmicpc.net/problem/2606

2606번: 바이러스

 

접근 방식)

컴퓨터의 수(노드)와 네트워크 쌍(엣지)가 주어진다.

1번 컴퓨터를 통해 DFS로 1번을 제외하고 DFS 타고 들어가는 횟수를 구하면 된다.

 

DFS, BFS 방식으로 모두 풀어볼 계획 → BFS가 더 빨랐다.

 

1) DFS

package tony_git.graph_traversal;

import java.util.*;
public class B_2606_DFS {
    static ArrayList<Integer>[] A;
    static boolean[] visited;
    static int count;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int computers = sc.nextInt();
        int networks = sc.nextInt();
        A = new ArrayList[computers + 1];
        visited = new boolean[computers + 1];

        for (int i = 1; i <= computers; i++)
            A[i] = new ArrayList<>();

        for (int i = 0; i < networks; i++) {
            int s = sc.nextInt();
            int e = sc.nextInt();
            A[s].add(e);
            A[e].add(s);
        }

        DFS(1);
        System.out.println(count);
    }

    static void DFS(int node) {
        visited[node] = true;
        for (int i : A[node]) {
            if (!visited[i]) {
                DFS(i);
                count++;
            }
        }
    }
}

 

2) BFS

package tony_git.graph_traversal;

import java.util.*;
public class B_2606_BFS {
    static ArrayList<Integer>[] A;
    static boolean[] visited;
    static int count;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int computers = sc.nextInt();
        int networks = sc.nextInt();
        A = new ArrayList[computers + 1];
        visited = new boolean[computers + 1];

        for (int i = 1; i <= computers; i++)
            A[i] = new ArrayList<>();

        for (int i = 0; i < networks; i++) {
            int s = sc.nextInt();
            int e = sc.nextInt();
            A[s].add(e);
            A[e].add(s);
        }

        BFS(1);
        System.out.println(count);
    }

    static void BFS(int node) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(node);
        visited[node] = true;

        while(!queue.isEmpty()) {
            int now = queue.poll();
            for (int i : A[now]) {
                if (!visited[i]) {
                    queue.add(i);
                    visited[i] = true;
                    count++;
                }
            }
        }
    }
}