[백준 2606] 바이러스_ 자바Java

이 문제는 2가지 방법으로 풀었다.
1. DFS
2. Union Find

1. DFS

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

/**
 * 2021-08-27
 * BOJ 2606 - 바이러스 
 * Memory: 11,564KB
 * Execution Time: 84ms 
 */

public class BOJ2606 {
q
	static int answer;
	static int N, M;
	static boolean[][] matrix;
	static boolean[] isVisited;

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(in.readLine());
		M = Integer.parseInt(in.readLine());
		answer = -1;		// 1번 컴퓨터는 카운트되지 않도록 -1로 초기화
		matrix = new boolean[N + 1][N + 1];
		isVisited = new boolean[N + 1];

		// 네트워크 상에서 직접 연결되어있는 컴퓨터 관계 표시
		for (int i = 0; i < M; i++) {
			StringTokenizer st = new StringTokenizer(in.readLine(), " ");
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			matrix[from][to] = matrix[to][from] = true;
		}

		trace(1);
		System.out.println(answer);
	}

	private static void trace(int computer) {
		isVisited[computer] = true;
		answer++;
		
		for(int i = 1; i <= N; i++) {
			// 해당 컴퓨터와 연결이 되어있고 && 아직 체크하지 않은 컴퓨터인 경우 => trace()
			if(matrix[computer][i] && !isVisited[i])
				trace(i);
		}
	}
}

• DFS로 풀 때 trace하는 메서드 안에서 카운팅을 하기 때문에 1번 컴퓨터도 카운팅이 된다. 그래서 카운팅하는 변수를 -1로 초기화하였다.

2. Union Find

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

public class Main {
	static int N, M;
	static int[] parents;

	static void makeSet() { 
		for (int i = 1; i <= N; i++) {
			parents[i] = i;
		}
	}

	static int findSet(int a) {
		if (parents[a] == a)
			return a;
		return parents[a] = findSet(parents[a]); 
	}

	static boolean union(int a, int b) {
		int aRoot = findSet(a);
		int bRoot = findSet(b);
		if (aRoot == bRoot)
			return false;

		parents[bRoot] = aRoot;
		return true;
	}

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(in.readLine());
		M = Integer.parseInt(in.readLine());

		parents = new int[N + 1];
		makeSet();
		for (int i = 0; i < M; i++) {
			StringTokenizer st = new StringTokenizer(in.readLine(), " ");
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());

			union(a, b);
		}
		int cnt = 0;
		int bias = findSet(1);
		for (int i = 2; i <= N; i++) {
			if (bias == findSet(i)) {
				cnt++;
			}
		}

		System.out.println(cnt);
		in.close();
	}
}

• Union Find로 풀 때는 연결된 정보에 기반하여 집합을 만들어주고, 1번 컴퓨터와 같은 집합에 속한 컴퓨터들을 카운팅 해주었다.