[BOJ/JAVA] 백준 2606번 : 바이러스

2606번: 바이러스

 

---

 

• 생각

문제를 보면 무조건 1과 연결되어 있는 컴퓨터 개수를 새는 문제이다.

 

컴퓨터 1과 연결되어 있으면 계속 깊이탐색을 해서 연결된 컴퓨터 갯수를 카운트하면 답은 쉽게 나온다.

 

• 코드

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static int a, b, answer;
	static boolean[][] graph;	
	static boolean[] check;	

	public static void main(String[] args) throws Exception {
		SetData();
		dfs(1);
		System.out.println(answer);
	}

	private static void SetData() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		a = Integer.parseInt(br.readLine());
		b = Integer.parseInt(br.readLine());

		graph = new boolean[a + 1][a + 1];
		check = new boolean[a + 1];

		for (int i = 1; b >= i; ++i) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int first = Integer.parseInt(st.nextToken());
			int second = Integer.parseInt(st.nextToken());
			graph[first][second] = true;
			graph[second][first] = true;
		}
	}
	
	static void dfs(int start) {
		check[start] = true;
		for (int i = 1; a >= i; ++i) {	        								
			if (graph[start][i] == true && check[i] == false) {
					dfs(i);		
					answer++;	
				}
			}
		}
}