[백준] 2606_바이러스 / DFS 그래프

 

 

Sliver

 

 

문제

 

신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다.

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

 

예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자.

1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다.

하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.

어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다.

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

 

 

입력

 

첫째 줄에는 컴퓨터의 수가 주어진다.

컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다.

둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다.

이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.

 

 

출력

 

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

 

 

 

---

 

풀이

 

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

class Main {
    static boolean[] visited;
    static ArrayList<ArrayList<Integer>> g;
    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());

        g = new ArrayList<>();
        visited = new boolean[n+1];

        for(int i=0; i<=n; i++){
            g.add(new ArrayList<>());
        }
        
        StringTokenizer st;
        for(int i=0; i<m; i++){
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            g.get(u).add(v);
            g.get(v).add(u);
        }

        visited[1] = true;
        dfs(1);
       
        System.out.println(count);
        br.close();
    }

    public static void dfs(int node){
        for(int i=0; i<g.get(node).size(); i++){
            int newnode = g.get(node).get(i);
            if(!visited[newnode]){
                visited[newnode] = true;
                count += 1;
                dfs(newnode);
            }
        }
    }
}

 

 

해결방법

 

1. ArrayList<ArrayList<Integer>> g 에 인접 노드들에 대한 정보를 담는다.

 

2. 방문을 탐색할 수 있는 visited[] 배열을 생성한다. 

 

3. DFS를 통해 노드들을 탐색한다.

• 1번 노드부터 시작하여 노드를 재귀적으로 반복하여 탐색한다.
  (이때 1번 노드는 탐색에서 제외하기 위해 visited[1] 을 true로 세팅한다)
• 방문하지 않은 노드를 방문할 때마다 count를 증가시키고, visited를 true로 세팅한다. 

 

 

 

---

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