[BOJ] 2606번 바이러스 for JAVA BFS 활용한 풀이

 

문제 바로가기

2606번: 바이러스

 

문제풀이

바이러스에 감염된 컴퓨터를 확인하기 위해 컴퓨터끼리의 연결상태를 확인해야한다.
컴퓨터끼리의 연결상태를 인접행렬로 표시한다.(연결되어있으면 1로 표기 )
감염된 컴퓨터를 큐에 넣고, 큐가 빌때까지 반복하면서 해당 컴퓨터와 연결된 컴퓨터를 감염시킨다.(BFS)

변수

• computer : 컴퓨터의 감염여부를 담는 boolean 배열
• map : 컴퓨터끼리 연결상태를 나타나는 2차원 인접행렬
• q : 바이러스에 감염된 컴퓨터를 확인하기 위해 BFS에서 사용하는 큐

로직 구현

1. findVirus(1)을 통해 1번 컴퓨터와 연결된 컴퓨터는 감염 표기하고 큐에 넣기
2. 큐가 빌때까지 큐에 들어있는 컴퓨터를 확인하면서 감염되었으면 감염표기하고 q에 넣기를 반복
3. 감염된 컴퓨터를 카운팅하여 출력 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int C, N, res, map[][];
	static boolean computer[];
	static StringTokenizer st;
	static Queue<Integer> q;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		C = Integer.parseInt(br.readLine());
		N = Integer.parseInt(br.readLine());
		res = 0;
		q = new LinkedList<Integer>();
		computer = new boolean[C + 1];
		map = new int[C+1][C+1];

		for (int n = 0; n < N; n++) {
			st = new StringTokenizer(br.readLine(), " ");
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			map[start][end] = 1;
			map[end][start] = 1;
		}
		findVirus(1);
		for (int c = 2; c <= C; c++) {
			if (computer[c])
				res++;
		}
		System.out.println(res);
	}
	
	private static void findVirus(int idx) {
		q.offer(idx);
		computer[idx] = true;
		
		while (!q.isEmpty()) {
			int cur = q.poll();
			for(int i=1; i<=C;i++)
			if (!computer[i] && map[cur][i]==1) {
					computer[i] = true;
					q.offer(i);
			}
		}
	}

}