[백준] 바이러스 2606 - JAVA

문제

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

2606번: 바이러스

 

코드

bfs

import java.io.*;
import java.util.*;

public class Main {	 

	static ArrayList<Integer> arr [];
	static boolean check[];
	static int result;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int n = Integer.parseInt(br.readLine());
		int m = Integer.parseInt(br.readLine());
		
		arr = new ArrayList [n+1];
		check = new boolean[n+1];
		
		for(int i=0;i<=n;i++) {
			arr[i] = new ArrayList<>();
		}
		
		for(int i=0;i<m;i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			arr[a].add(b);
			arr[b].add(a);
		}
		
		bfs(1);
		
		System.out.print(result);
		
	}
	
	static void bfs(int start) {
		Queue<Integer> que = new LinkedList<>();
		
		que.add(start);
		check[start] = true;
		
		result = 0;
		
		while(!que.isEmpty()) {
			int cur = que.poll();
			
			for(int next : arr[cur]) {
				if(check[next]) continue;
				
				check[next] = true;
				que.add(next);
				result = result+1;
			}
		}
	}
}

dfs

import java.io.*;
import java.util.*;

public class Main {	 

	static ArrayList<Integer> arr [];
	static boolean check[];
	static int result;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int n = Integer.parseInt(br.readLine());
		int m = Integer.parseInt(br.readLine());
		
		arr = new ArrayList [n+1];
		check = new boolean[n+1];
		
		for(int i=0;i<=n;i++) {
			arr[i] = new ArrayList<>();
		}
		
		for(int i=0;i<m;i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			arr[a].add(b);
			arr[b].add(a);
		}
		
		dfs(1);
		
		System.out.print(result);
		
	}
	
	static void dfs(int cur) {
		
		check[cur] = true;
				
		for(int next : arr[cur]) {
			if(!check[next]) {
				dfs(next);
				result = result+1;
			}
		}
	}
}