[백준] 2606번 : 바이러스

2606번: 바이러스

---

문제

---

예제

---

풀이

DFS(깊이 우선 탐색) 와 BFS(넓이 우선 탐색)을 활용한 대표적인 문제이다.

[백준] 1260번 : DFS와 BFS

1260번 문제를 통해서 DFS와 BFS의 구조와 방식을 이해했다면 크게 어렵지않은 문제이다.

사실 이번 문제에서는 DFS와 BFS 어떤걸 사용해도 해결이 가능하다.

---

소스 코드

방법 1 : DFS

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

public class Main {

    static int N; // 컴퓨터의 수 ( 정점의 수 )
    static int M; // 컴퓨터 쌍의 수 ( 간선의 수 )
    static int cnt = 0;

    static int[][] check;
    static boolean[] visit;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());

        check = new int[101][101];
        visit = new boolean[101];

        for (int i = 1; i <= M; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            check[x][y] = check[y][x] = 1;
        }

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

    }

    public static int DFS(int start) {
        visit[start] = true;

        for (int i = 1; i <= N; i++) {
            if (check[start][i] == 1 && visit[i] == false) {
                cnt++;
                DFS(i);
            };
        }

        return cnt;
    }
}

 

방법 2 : BFS

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; // 컴퓨터의 수 ( 정점의 수 )
    static int M; // 컴퓨터 쌍의 수 ( 간선의 수 )
    static int cnt = 0;

    static int[][] check;
    static boolean[] visit;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());

        check = new int[101][101];
        visit = new boolean[101];

        for (int i = 1; i <= M; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            check[x][y] = check[y][x] = 1;
        }

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

    }

    public static int BFS(int start) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(start);
        visit[start] = true;

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

            for (int i = 1; i <= N; i++) {
                if (check[tmp][i] == 1 && visit[i] == false) {
                    q.offer(i);
                    visit[i] = true;
                    cnt++;
                };
            }
        }
        return cnt;
    }
}