[백준] 2606번 바이러스 (Java)

문제 Silver3

---

풀이

그래프 탐색(DFS)를 통해 인접 정점의 개수를 구하는 문제.

인접행렬을 boolean형으로 선언해

탐색하는 인덱스의 값이 true이고 visited배열이 false라면 탐색하며, 결과값 cnt 증가.

 

코드

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

public class Main{
	static boolean[][] arr;
	static boolean[] visited;
	static int N, cnt;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		arr = new boolean[N+1][N+1];
		visited = new boolean[N+1];
		cnt = 0;
		int M = Integer.parseInt(br.readLine());
		for(int i =0 ; i < M ; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine()," ");
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			arr[from][to] = true;
			arr[to][from] = true;
		}
		dfs(1);
		System.out.println(cnt);
	}
	
	public static void dfs(int start) {
		visited[start] = true;
		for(int i = 1 ; i <= N ; i++) {
			if(arr[start][i] && !visited[i]) {
				dfs(i);
				cnt++;
			}
		}
	}
}