[알고리즘] 백준 2606 바이러스

www.acmicpc.net/problem/2606

2606번: 바이러스

 

public class BOJ_2606 {

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

        int[][] map = new int[n + 1][n + 1];
        boolean[] visited = new boolean[n + 1];

        for (int i = 0; i < n + 1; i++) {
            Arrays.fill(map[i], 0);
        }

        for (int i = 0; i < m; i++) {
            String s = br.readLine();
            StringTokenizer st = new StringTokenizer(s, " ");
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            map[x][y] = 1;
            map[y][x] = 1;
        }

        Queue<Integer> queue = new LinkedList<Integer>();
        queue.add(1);
        visited[1] = true;
        int count = 0;

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

            for (int i = 1; i < visited.length; i++) {
                if (!visited[i] && map[k][i] == 1) {
                    queue.add(i);
                    visited[i] = true;
                    count++;
                }
            }
        }

        System.out.println(count);
    }
}

맨 처음 바이러스가 감염된 컴퓨터로부터 인접 노드부터 차례대로 감염이 된다고 하였을 때, 감염된 컴퓨터의 대수를 카운트 하는 문제이다.

 

인접 노드부터 차례대로 감염이 된다고 하여서 BFS로 문제를 풀긴 하였는데,

 

단순 카운트 문제여서 DFS로 풀어도 문제는 없을것이다.