[백준] 2606 바이러스 - Java

문제 - 바이러스

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

 

 

 

 

 

접근 방법

 

이 문제는 그래프 완전 탐색 문제이다

너비 우선 탐색(BFS), 깊이 우선 탐색(DFS)  둘중에 한개를 활용하여 풀 수 있는 문제이다

---

코드 작성 (BFS)

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

public class Main {
    static int N;
    static List<List<Integer>> map;
    static boolean[] visited;
    static int result;

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

            int count = Integer.parseInt(br.readLine());
            visited = new boolean[N + 1];
            map = new ArrayList<>();

            for (int i = 0; i <= N; i++) {
                map.add(new ArrayList<>());
            }

            StringTokenizer st;
            result = 0;
            for (int i = 0; i < count; i++) {
                st = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                map.get(x).add(y);
                map.get(y).add(x);
            }

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


    }

    public static void bfs(int start) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);

        while (!queue.isEmpty()) {
            int now = queue.poll();

            if (!visited[now]) {
                result++;
                visited[now] = true;

                for (int n : map.get(now)) {
                    if (!visited[n]) {
                        queue.add(n);
                    }
                }
            }
        }
    }


}

---

코드 작성 (DFS)

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

public class Main {
    static int N;
    static List<List<Integer>> map;
    static boolean[] visited;
    static int result;

    public static void main(String[] args) throws IOException {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            int N = Integer.parseInt(br.readLine());
            int count = Integer.parseInt(br.readLine());
            visited = new boolean[N + 1];
            map = new ArrayList<>();

            for (int i = 0; i <= N; i++) {
                map.add(new ArrayList<>());
            }
            StringTokenizer st;
            for (int i = 0; i < count; i++) {
                st = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                map.get(x).add(y);
                map.get(y).add(x);
            }
            result = 0;

            dfs(1);

            System.out.println(result - 1);
        }

    }

    public static void dfs(int start) {
        if (!visited[start]) {
            visited[start] = true;
            result++;

            for (int i : map.get(start)) {
                dfs(i);
            }
        }
    }
}