Boj 2606 바이러스

문제 링크 : https://www.acmicpc.net/problem/2606

DFS Ver)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Boj_2606_dfs_ver {

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer st;
	static int n, m, v;
	static int map[][];
	static boolean[] visited;
	static int answer ;
	public static void main(String[] args) throws IOException {

		n = Integer.parseInt(br.readLine());

		m = Integer.parseInt(br.readLine());

		map = new int[n + 1][n + 1];
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			map[a][b] = 1;
			map[b][a] = 1;
		}

		visited = new boolean[n+1];
		visited[1]=true;
		answer=0;
		dfs(1);

		System.out.println(answer);
	}

	private static void dfs(int start) {
		visited[start] = true;

		for(int i=0; i<=n; i++) {
				if(map[start][i]==1&&!visited[i]) {
					dfs(i);
					answer++;
			}
		}
	}

}

BFS Ver)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Boj_2606_bfs_ver {

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer st;
	static int n, m, v;
	static int map[][];
	static boolean[] visited;
	static int answer ;
	public static void main(String[] args) throws IOException {

		n = Integer.parseInt(br.readLine());
		map = new int[n + 100][n + 100];

		m = Integer.parseInt(br.readLine());

		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			map[a][b] = 1;
			map[b][a] = 1;
		}

		visited = new boolean[n+1];
		visited[1]=true;
		answer=0;
		bfs(1);

		System.out.println(answer);
	}

	private static void bfs(int start) {

		Queue<Integer> queue = new LinkedList<Integer>();
		queue.offer(start);

		visited[start] = true;

		 while(!queue.isEmpty()) {

			 int temp = queue.poll();
			 for(int i=0; i<=n;i++) {
				 if(map[temp][i]==1&&!visited[i]) {
					 queue.offer(i);
					 visited[i]=true;
					 answer++;
				 }
			 }
		 }
	}

}