백준 문제 풀이 : 바이러스 2606

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

2606번: 바이러스

 

 

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

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

 

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

 

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

 

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

 

DFS 로 푸는 대표적인 문제인 바이러스 찾기 문제이다
내가 생각하는 이 문제의 포인트는 컴퓨터끼리 연결된 네트워크 즉, '선' 에 대해서 생각을 해봐야 한다.
즉 1번 컴퓨터와 2번 컴퓨터가 연결되었다고 했을 때 단순히 1-2 에만 선이 있는게 아니라 2-1 도 선 edge 가 있다고 생각해야한다. 이것을 코드로 옮기면 1,2 좌표에만 값이 있는 게 아니라 2,1 에도 똑같이 값이 있어야한다
이 점을 기억해두면 추후 재귀함수 돌릴때 1번 컴퓨터에서 2번 컴퓨터로 바이러스가 넘어가면 다음 바이러스가 넘어가는 지점은(탐색하는 지점) 은 2,1 이 아닌 2번에서 연결된 컴퓨터임을 알 수 있다.

 

package baekJoon;

import java.util.ArrayList;
import java.util.Scanner;

// <https://www.acmicpc.net/problem/2606>
public class Quiz_2606_Virus {

    static int vex, edge; // vex 는 컴퓨터 edge 는 컴퓨터와 연결된 네트워크의 수

    static int count = 0; // 최종 감염된 컴퓨터의 갯수
    static boolean[] ch; // 방문한 컴퓨터 배열
    static int[][] graph; // 컴퓨터간 연결된 네트워크 구조

    public static void dfs(int n) {

//            System.out.println(n);
        ch[n] = true; // n 번째 컴퓨터에 방문함=> 바이러스에 감염됨

        for (int i = 1; i <= vex; i++) { // 1번째 컴퓨터부터 전체 컴퓨터에 대해서 탐색 시작
//            System.out.println(i + " : " + n);

            if (graph[n][i] == 1 && !ch[i]) { // 해당 컴퓨터에는 방문하지 않아야 하며, 컴퓨터끼리 연결되어있어야함
                // 즉 ch 배열에서 해당 컴퓨터는 false 감염되지 않은 상태 이여야하고, graph 에서는 값이 있어야함
//                System.out.println(i + " : " + n);

                count++; // 방문가능 -> 감염된 경우 count+1
                dfs(i); // 현재 방문한 n 번째 컴퓨터 말고 n 번째와 연결된 i 번째 컴퓨터에 방문함
            }
        }

    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        vex = scanner.nextInt();
        edge = scanner.nextInt();

        ch = new boolean[vex + 1]; // 1번째 컴퓨터부터 계산해야함으로 입력받은 컴퓨터의 수 +1 배열
        graph = new int[vex + 1][vex + 1];
//        Arrays.fill(ch, false);

        for (int i = 0; i < edge; i++) {
            int num1 = scanner.nextInt();
            int num2 = scanner.nextInt();

            // 컴퓨터의 1과 4가 연결된 것이나 4와 1이 연결된 것이나 같은 의미 임으로
            // 1 번 컴퓨터와 4번 컴퓨터가 들어오면 1,4 도 1로 두고, 4,1 도 1로 둠
            // 즉 1,4 와 4,1 이 연결된 것을 확인가능
            graph[num1][num2] = graph[num2][num1] = 1;

        }

        //ch[1] = true;
        dfs(1);
        System.out.println(count);

    }
}