알고리즘/그래프 이론
[백준 2606] 바이러스 Java 문제 풀이
빠르게 핵심만
2024. 4. 29. 01:12
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;
}
}