[백준 2606번] 바이러스

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

2606번: 바이러스

그래프를 이용해서 푸는 문제입니다.

---

풀이법

문제를 보면 1번 컴퓨터와 연결되있는 컴퓨터들은 모두 바이러스에 걸리므로, 1번 컴퓨터와 연결되있는 2 5 그리고 그 두 컴퓨터와 이어져있는 3 6까지 총 4개의 컴퓨터들은 바이러스에 걸리고, 4 7 컴퓨터만 무사한것으로 볼 수 있습니다. 따라서 해결법은

1. 입력 간선을 모두 정점 노트의 다음 노드에 저장한다.( 예 1-2를 정점이 1인 노드의 다음 노드 값엔 2를 저장)
2. DFS 또는 BFS를 이용하며 그래프를 탐색하는데. 한번 방문한 노드는 방문하지 않는다.
3.방문하면서 해당 컴퓨터를 카운트해주면, 마지막에는 바이러스에 걸린 컴퓨터를 알게 된다.

 

코드

import java.util.*;
import java.io.*;
public class Main {
	static int count=0;
	public static void main(String arg[]) {
		//입력단계
		Scanner sc= new Scanner(System.in);
		int n=sc.nextInt();
		int k=sc.nextInt();
		int firstNode=0;
		int nextNode=0;
		ArrayList<Integer>[] arr= new ArrayList[101];
		for(int i=0; i<=100;i++)
			arr[i]=new ArrayList<Integer>();
		boolean []visted=new boolean[n+1];
		Arrays.fill(visted, false);
		//입력받은 간선들을 각 노드의 정점 배열에 저장
		for(int i=0;i<k;i++) {
			firstNode=sc.nextInt();
			nextNode=sc.nextInt();
			arr[firstNode].add(nextNode);
			arr[nextNode].add(firstNode);
		}
		//만약 정점이 하나가 아닐경우 계산
		if(n!=1)
			DFS(arr,1,visted);
		
		System.out.println(count);
		
	}
	public static void DFS(ArrayList<Integer>[] arr,int n,boolean []visted){
		visted[n]=true;
		if(n!=1)//시작 지점이 아닐시 계산
			count++;
		for (int i :arr[n]) {//이미 방문했는지 확인 
			if(visted[i]==false) {
				DFS(arr,i,visted);
			}
			
		}
		
	
		
	}

	

}