[백준(Baekjoon)][자바(java)] 2606 : 바이러스 / DFS와 BFS

 

www.acmicpc.net/problem/2606

2606번: 바이러스

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class Main {
	
	static int c, cnt, edge[][];
	static boolean visited[];
	
	public static void cntVirusCom_BFS( int s ) {
		Deque<Integer> queue = new ArrayDeque<>();
		visited = new boolean[c+1];
		queue.add( s );
		while( !queue.isEmpty() ) {
			int v = queue.remove();
			if( visited[v] )  continue;
			else  visited[v] = true;
			cnt++;	// 현재 정점과 인접해있는 정점들의 개수를 더함
			for( int u = 1; u <= c; u++ )
				if( edge[v][u] == 1 && !visited[u] ) 	
					queue.add( u );
		}
	}

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader( new InputStreamReader(System.in) );
		c = Integer.parseInt( br.readLine() );
		int t = Integer.parseInt( br.readLine() ), i, j;
		int n[][] = new int[t][2];
		for( i = 0; i < t; i++ ) {
			StringTokenizer st = new StringTokenizer( br.readLine() );
			for( j = 0; j < 2; j++ )
				n[i][j] = Integer.parseInt( st.nextToken() );
		}
		br.close();
		
		edge = new int[c+1][c+1];
		for( i = 0; i < t; i++ )
			edge[n[i][0]][n[i][1]] = 1;
		for( i = 0; i < t; i++ )
			edge[n[i][1]][n[i][0]] = 1;
		
		cntVirusCom_BFS( 1 );
		System.out.println( cnt-1 );

	}
}