백준 2606번 - 바이러스

문제링크

문제

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

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

 

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

 

입력

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

출력

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

예제 입력 1 

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

예제 출력 1 

4

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

 

문제 풀이 과정

문제의 핵심은 1과 연관된 노드를 방문하는 수를 구하는 것이다.

 

1이 바이러스에 걸렸으므로 1부터 시작한다. 1부터 시작하므로 노드 방문을 했으니 visitied 배열에 1부분에 true 로 바꿔준다

 

1은 2 와 5와 연결 되어 있다. 탐색은 순차적으로 하므로 1다음에 탐색할 노드는 2이다.

2는 1, 3, 5와 연결 되어 있다. 이 중에서 1은 visited 배열에서 true 로 되어 있으므로 탐색을 하지 않고 그다음 노드인 3을 탐색을 하게 된다.

 

3은 2와 연결 되어 있지만 2는 이미 방문한 적이 있으므로 탐색을 하지 않고 탐색을 종료 한다.

 

 

2와 연결된 마지막 노드인 5로 다시 탐색이 들어간다.

5는 1, 2, 6과 연결되어 있지만 1 과 2는 visitied 배열에 true 로 되어 있으므로 6으로 탐색이 들어간다.

 

6은 5와 연결되어 있지만 5는 visited 배열에 true 로 되어 있으므로 탐색을 종료 한다.

 

 

 

그럼 윗 부분 노드는 모두 탐색이 종료 된다.

1과 2다음으로 연결된 노드인 5로 탐색이 들어가게 된다.

하지만 5는 이미 탐색한 적이 있으므로 탐색이 최종으로 종료가 된다.

 

1로 인해서 전염된 컴퓨터의 개수를 구하는 문제이므로 visited 배열에서 index = 1을 제외한 true 의 개수를 출력하면된다.

 

 

바이러스는 서로 연결되어 있는 컴퓨터 모두 전염이 되기 때문에 방향이 없는 그래프로 구현했으며, 컴퓨터는 서로 연결 되어 있기 때문에 ArrayList 양쪽에 데이터를 저장했다.

 

for (int i = 0; i < M; i++) {
    st = new StringTokenizer(br.readLine());
    int s = Integer.parseInt(st.nextToken());
    int e = Integer.parseInt(st.nextToken());

    list[s].add(e);
    list[e].add(s);
}

 

연결된 노드를 탐색하기 위해서 DFS 메소드를 구현하였다.

숫자를 방문했는지 확인하는 visitied 배열에 현재 숫자 방문했다는 것을 표시하는 의미로 true 로 변환한다.

그 후 현재 숫자와 연결되어 있는 숫자에서 방문한적이 없으면 DFS 를 호출하여 재 탐색을 한다.

 

public static void DFS(int cur){
    visitied[cur] = true;
    for(int item : list[cur]){
        if(!visitied[item]){
            DFS(item);
        }
    }
}

 

최종 코드

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

public class Main {
    public static ArrayList<Integer>[] list;
    public static boolean[] visitied;
    
    public static void DFS(int cur){
        visitied[cur] = true;
        for(int item : list[cur]){
            if(!visitied[item]){
                DFS(item);
            }
        }
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        int M = Integer.parseInt(st.nextToken());

        list = new ArrayList[N+1];
        visitied = new boolean[N+1];

        for (int i = 0; i < N+1; i++) {
            list[i] = new ArrayList<Integer>();
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());

            list[s].add(e);
            list[e].add(s);
        }

        DFS(1);
        int cnt = 0;
        for(boolean item : visitied){
            if(item){
                cnt++;
            }
        }
        System.out.println(cnt-1);
    }
}