[JAVA] 백준 2606번 : 바이러스 (DFS)

www.acmicpc.net/problem/2606

문제

입력의 첫째 줄이 그래프의 노드 갯수가 되고 둘째 줄이 간선의 갯수가 될 것이다.
또한 무방향 그래프가 될것이다. 

해결 방안

무방향 그래프를 ArrayList를 이용하여 구현하였다.

1번부터 시작하는 DFS 탐색을 하였으며 DFS의 depth를 바이러스 감염 시킨 컴퓨터 갯수로 하였다.

코드

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

// 바이러스
public class Main {
	
	static int n; // v
	static int e; // edge
	static ArrayList<ArrayList<Integer>> graph;
	static boolean[] visited;
	static int cnt; // 결과

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		e = Integer.parseInt(br.readLine());
		
		graph = new ArrayList<>();
		visited = new boolean[n+1];
		for(int i=0; i<=n; i++) {
			graph.add(new ArrayList<Integer>());
		}
		
		String str;
		int v1, v2;
		for(int i=0; i<e; i++) {
			str = br.readLine();
			v1 = Integer.parseInt(str.split(" ")[0]);
			v2 = Integer.parseInt(str.split(" ")[1]);
			
			graph.get(v1).add(v2);
			graph.get(v2).add(v1);
		}
		
		// ==== 입력 끝
		cnt = 0;
		dfs(1);
		
		System.out.println(cnt);
	}
	
	static void dfs(int start) {
		
		visited[start] = true;
		
		int y;
		for(int i=0; i<graph.get(start).size(); i++) {
			y = graph.get(start).get(i);
			
			if(!visited[y]) {
				visited[y] = true;
				cnt++;
				dfs(y);
			}
		}
	}

}