[BOJ 2606번] 바이러스(JAVA)

www.acmicpc.net/problem/2606

2606번: 바이러스

import java.io.*;
import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

class Main{
	
	static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
	static StringBuilder sb=new StringBuilder();
	static int N, M;
	static int[][] arr;
	static int[] virus;
	
	public static void main(String args[]) throws Exception {
		N=Integer.parseInt(br.readLine());
		M=Integer.parseInt(br.readLine());
		arr=new int[2*M][2];
		virus=new int[N+1];
		for(int i=0;i<M;i++) {
			String str[]=br.readLine().split(" ");
			arr[2*i][0]=Integer.parseInt(str[0]);
			arr[2*i][1]=Integer.parseInt(str[1]);
			arr[2*i+1][0]=arr[2*i][1];
			arr[2*i+1][1]=arr[2*i][0];
		}
		function(1);
		int cnt=0;
		for(int n:virus) {
			if(n==1) cnt++;
		}
		System.out.println(cnt-1);
	}
	
	public static void function(int n) {
		if(virus[n]==1) return;
		virus[n]=1;
		for(int i=0;i<2*M;i++) {
			if(arr[i][0]==n) {
				function(arr[i][1]);
			}
		}
	}
	
}

arr은 경로를 저장하는 이중배열인데요, arr[i][0]에는 i번째 경로의 시작점, arr[i][0]에는 i번째 경로의 끝지점을 저장했는데요, 경로는 양방향으로 나아갈 수 있으므로 끝지점과 시작점을 바꿔서 한번 더 저장을 해주었습니다.

virus는 i번째 컴퓨터의 감염 여부는 나타내는 배열인데, 감염되었을 경우 1, 그렇지 않을 경우 0을 저장해주었습니다.

function이라는 함수에서 n을 매개변수로 받아 virus[n]은 감염된 바이러스로 체크하고, n을 시작점으로 하여 연결된 끝점 arr[i][1]에 대해 재귀를 이용해 function을 다시 호출해주었습니다.