[백준 2606] 바이러스 Java 문제 풀이

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

 

접근

BFS 또는 DFS를 이용하여 바이러스에 걸리게 되는 컴퓨터의 수를 구할 수 있습니다. 1번 노드를 시작으로 인접한 노드를 우선적으로 탐색하는 것이 효율적이라고 판단하여 BFS를 사용했습니다.

 

코드

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

public class Main {
	static int n, m;
	static boolean[][] graph;

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

		// 입력 처리
		n = Integer.parseInt(br.readLine());
		m = Integer.parseInt(br.readLine());

		graph = new boolean[n + 1][n + 1];

		while (m-- > 0) {
			st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			graph[u][v] = graph[v][u] = true;
		}

		// 바이러스에 걸리게 되는 컴퓨터의 수를 찾는다.
		int count = bfs();

		// 결과 출력
		System.out.println(count);
	}

	static int bfs() {
		Queue<Integer> bfsQ = new ArrayDeque<>();
		bfsQ.offer(1);

		boolean[] visited = new boolean[n + 1];
		visited[1] = true;

		int count = 0;
		while (!bfsQ.isEmpty()) {
			Integer curr = bfsQ.poll();
			for (int i = 1; i <= n; i++) {
				if (graph[curr][i] && !visited[i]) {
					bfsQ.offer(i);
					visited[i] = true;
					count++;
				}
			}
		}

		return count;
	}
}