백준 2606번 바이러스 자바 풀이

❓문제

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

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

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

---

🔠 입력

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

 

---

🖨️출력

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

---

✍️ 예제 입력

7
6
1 2
2 3
1 5
5 2
5 6
4 7

✔️ 예제 출력

4

---

💡해설

빠른길이 아니라 연결된 컴퓨터를 전부 찾는 것이기 때문에 깊이우선탐색 DFS를 이용해야 한다.

입력받을 때 연결된 컴퓨터 값을 배열에 전부 넣고 1로 세팅한다.

visited배열에 false로 초기화한 후 방문한 컴퓨터는 true로 바꿔준다.

 

1번 컴퓨터와 연결된 컴퓨터를 찾는 것이기 때문에 dfs함수안에서만 for문으로 찾으면 된다. 

 

 

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

public class Main {
    
    static int[][] computers;
    static boolean[] visited;
    static int count = 0;
    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());

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

        Arrays.fill(visited, false);

        computers[0][0] = computers[0][1] = 0;


        for(int i = 0; i < m; i++ ) {
            String input = br.readLine();
            int a = Integer.parseInt(input.split(" ")[0]);
            int b = Integer.parseInt(input.split(" ")[1]);
            
            computers[a][b] = 1;
            computers[b][a] = 1;
        }
        
        visited[1] = true; 
        dfs(1);

        System.out.println(count);
       
    }
    private static void dfs(int x) {
        for(int i = 1; i < computers.length; i++) {
            if(computers[x][i] == 1 && !visited[i]) {
                visited[i] = true;
                count++;
                dfs(i);
            }
        }

    }

}