백준 2606번 java 바이러스

 

2606번: 바이러스

 

DFS, BFS 모두 사용 가능한 문제이다.

1번 컴퓨터와의 연결을 확인해야 하기 때문에 배열을 초기화할때 입력된 두 수의 배열을 모두 1로 초기화시켜준다.

시작지점은 무조건 1번 컴퓨터이기 때문에 1번부터 탐색을 해주면 된다.

 

 

-BFS-

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class 2606 {

	static int com_cnt, conn_cnt;
	static int[][] computer;
	static boolean[] check;
	static int count;

	static void bfs(int x) {
		Queue qu = new LinkedList();
		qu.add(x);

		while (!qu.isEmpty()) {
			x = qu.poll();
			check[x] = true;
			for (int i = 1; i < com_cnt + 1; i++) {
				if (!check[i] && computer[x][i] == 1) {
					check[i] = true;
					qu.add(i);
					count++;
				}
			}
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		com_cnt = sc.nextInt();
		conn_cnt = sc.nextInt();

		computer = new int[com_cnt + 1][com_cnt + 1];
		check = new boolean[com_cnt + 1];

		for (int i = 0; i < conn_cnt; i++) {
			int a1 = sc.nextInt();
			int a2 = sc.nextInt();
			computer[a1][a2] = computer[a2][a1] = 1;
		}
		bfs(1);
		System.out.println(count);
	}
}

 

 

-DFS-

import java.util.Scanner;

public class 2606 {

	static int n, m;
	static int[][] computer;
	static boolean[] visit;
	static int count;

	static void dfs(int x) {
		visit[x] = true; //

		for (int i = 1; i < n + 1; i++) {
			if (!visit[i] && computer[x][i] == 1) {
				dfs(i);
				count++;
			}
		}

	}

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		n = sc.nextInt(); // 컴퓨터 개수
		m = sc.nextInt(); // 1번컴퓨터와 연결된 컴퓨터

		computer = new int[n + 1][n + 1];
		visit = new boolean[n + 1];

		for (int i = 0; i < m; i++) {
			int p1 = sc.nextInt();
			int p2 = sc.nextInt();
			computer[p1][p2] = computer[p2][p1] = 1; // 연결된 컴퓨터를 1로 초기화
		}

		dfs(1);
		System.out.println(count);

	}

}