백준 2606 바이러스 (Java)

1. 문제 링크

2606번: 바이러스

 

2. 문제 및 입출력예제

 

3. 문제 풀이

인접행렬을 이용해서 무향 그래프를 연결시켰다.

1번을 큐에 넣고 큐가 빌 때까지 반복한다.

큐에서 꺼낸 정점의 인접 정점들을 큐에 넣고 방문처리를 한다.

큐에 들어갔던 정점의 수를 함께 세고, 마지막에 1을 빼고 출력한다.

 

4. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Queue;

public class Main {
	static int V, E, adjMatrix[][], cnt;
    public static void main(String[] args) throws IOException{
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       V = Integer.parseInt(br.readLine());
       E = Integer.parseInt(br.readLine());
       adjMatrix = new int[V][V];
       String[] split = new String[2];
       int from, to;
       for(int i=0;i<E;i++) {
    	   split = br.readLine().split(" ");
    	   from = Integer.parseInt(split[0])-1;
    	   to = Integer.parseInt(split[1])-1;
    	   adjMatrix[from][to] = adjMatrix[to][from] = 1;
       }
    		   
       bfs();
       
       System.out.println(cnt-1);
	}
	private static void bfs() {
		Queue<Integer> queue = new ArrayDeque<>();
		boolean[] visit = new boolean[V];
		queue.offer(0);
		visit[0] = true;
		
		while(!queue.isEmpty()) {
			int current = queue.poll();
			cnt++;
			
			for(int i=0;i<V;i++) {
				if(adjMatrix[current][i] == 1 && !visit[i]) {
					queue.offer(i);
					visit[i] = true;
				}
			}
		}		
	}
}