문제

백준 2606번
https://www.acmicpc.net/problem/2606

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

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

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

첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.

1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.

• 위 그림 1과 아래 사진을 참조하면

• 컴퓨터 바이러스는 무조건 1번 컴퓨터가 걸린다.
• 그러므로 1번과 연결된 모든 컴퓨터를 찾으면 된다.
• 1변과 연결되어 있는 컴퓨터는 2, 3, 5, 6을 총 4대이므로 결과 4를 반환한다.

Code

Java

DFS로 풀 경우

import java.io.*;
import java.util.*;

public class Main {
    static int cnt = 0;  // 결과
    static boolean[] visited;  // 빙믄 확인
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int computer = Integer.parseInt(br.readLine());  // 컴퓨터 수
        int connect = Integer.parseInt(br.readLine());  // 연결 정보
        visited = new boolean[computer + 1];

        List<ArrayList<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < computer + 1; i++) {
            graph.add(new ArrayList<>());
        }

        for (int i = 0; i < connect; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            // 양방향 연결
            graph.get(from).add(to);
            graph.get(to).add(from);
        }
        System.out.println(dfs(graph, computer, 1));

    }

    public static int dfs(List<ArrayList<Integer>> graph, int computer, int start) {
    	// start 부분 방문 true
        visited[start] = true;

        for (int idx : graph.get(start)) {
        	// 방문하지 않았을 경우
            if (!visited[idx]) {
                dfs(graph, computer, idx);
                cnt++;
            }
        }
        return cnt;
    }
}

BFS로 풀 경우

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
    	// DFS와 공통 코드
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int computer = Integer.parseInt(br.readLine());
        int connect = Integer.parseInt(br.readLine());

        List<ArrayList<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < computer + 1; i++) {
            graph.add(new ArrayList<>());
        }

        for (int i = 0; i < connect; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            graph.get(from).add(to);
            graph.get(to).add(from);
        }
        System.out.println(bfs(graph, computer, 1));
    }

    public static int bfs(List<ArrayList<Integer>> graph, int computer, int start) {
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[computer + 1];
        // 시작부분 queue에 넣고 방문 true
        queue.offer(start);
        visited[start] = true;

        int cnt = 0;
        while (!queue.isEmpty()) {
            int cur = queue.poll();

            for (int i = 0; i < graph.get(cur).size(); i++) {
                int temp = graph.get(cur).get(i);

                if (!visited[temp]) {
                    visited[temp] = true;
                    queue.offer(temp);
                    cnt++;
                }
            }
        }
        return cnt;
    }
}