[BOJ] 2606 바이러스 [Java]

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

2606번: 바이러스

---

1. 문제 요약

1번이 바이러스에 걸리면, 1번과 연결된 모든 번호가 감염된다. 4번과 7번은 1번과 연결되어 있지 않으므로 감염되지 않는다.

연결 정보가 주어졌을 때, 1번을 시작으로 바이러스에 감염되는 컴퓨터의 수를 출력하라.

2. 풀이

그래프 문제이다. 해당 노드에 인접한 노드들을 따라 연결된 모든 노드들의 개수를 출력하면 된다.

갈 수 있는 모든 노드를 가기 때문에 DFS, BFS 모두 가능하다. 하지만 인접한 노드를 방문하기만 하면 되기 때문에

인접 노드 방문에 효율적인 BFS를 사용하였다. 전형적인 BFS 틀을 사용하였다. 

그래프를 구현하는 방법은 인접 행렬, 인접 리스트가 있다. 나는 인접 리스트로 풀어보았다.

 

 

3. 문제점

여러 방법으로 풀어볼 것

1. DFS

2. 인접행렬

 

4. 코드

BFS, 인접리스트

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

public class BOJ_2606_바이러스 {

	static boolean[] visited;
	static List<List<Integer>> list = new ArrayList<> ();
	static int N, ans;
	static int cnt;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		cnt = Integer.parseInt(br.readLine());
		visited = new boolean[N+1];
		
		for (int i = 0; i <= N; i++) {
			list.add(new ArrayList<>());
		}
		for (int i = 0; i < cnt; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int num1 = Integer.parseInt(st.nextToken());
			int num2 = Integer.parseInt(st.nextToken());
			list.get(num1).add(num2); //양방향 그래프
			list.get(num2).add(num1);
		}
		
		bfs(1);
		System.out.println(ans);
	}
	static void bfs(int start) {
		Queue<Integer> queue = new ArrayDeque<>();
		queue.add(start);
		visited[start] = true;
		while (!queue.isEmpty()) {
			int front = queue.poll();
			int len = list.get(front).size();
			for (int i = 0; i < len; i++) {
				int next = list.get(front).get(i);
				if (visited[next]) continue;
				queue.add(next);
				ans++; //인접 노드 개수 카운트
				visited[next] = true;
			}
		}
		
	}
}