[백준] 2606. 바이러스 (java)

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

2606번: 바이러스

 

문제설명

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

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

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

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

---

📗 풀이과정

컴퓨터들을 노드라고 생각하고, 1번 컴퓨터와 연결되어 있는 컴퓨터들을 DFS로 탐색하며 개수를 세었습니다.

 

 

전체코드

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

public class BJ2606_바이러스 {
	static Map<Integer,ArrayList<Integer>> map = new HashMap<>(); //연결된 컴퓨터 리스트
	static int virus=0;//바이러스에 감염되는 컴퓨터 수
	static boolean[] visited;//이미 바이러스에 걸린 컴퓨터인지 확인
	
	public static void main(String[] args) throws Exception{
		// TODO Auto-generated method stub

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int com=Integer.parseInt(br.readLine());//컴퓨터 수
		int node = Integer.parseInt(br.readLine());//연결된 컴퓨터 쌍 수
		
		for(int i=0;i<com;i++) map.put(i+1, new ArrayList<>());//컴퓨터 리스트 만들어주기
		
		String[] s;
		for(int i=0;i<node;i++) {
			s=br.readLine().split(" ");
			int a = Integer.parseInt(s[0]);//컴퓨터 쌍
			int b = Integer.parseInt(s[1]);
			
			map.get(a).add(b);//a컴퓨터와 연결된 리스트에 b추가
			map.get(b).add(a);
		}
		
		visited = new boolean[com+1];
		dfs(1);//1번부터 감염되기 때문에 1부터 시작하는 dfs
		
		System.out.println(virus-1);//1번을 제외해야 하기 때문에 -1해줌.
	}
    //감염된 컴퓨터 바이러스 확인
	static void dfs(int now) {
		
		//System.out.println(now);
		visited[now]=true;//바이러스 감염 여부 = true
		virus++;//바이러스에 감염된 컴퓨터 수 +1
		
		for(int i:map.get(now)) {//now컴퓨터와 연결된 컴퓨터 번호 가져오기
			if(!visited[i])//이미 바이러스에 감염되지 않았으면
				dfs(i);
		}
	}
}