Code up 4503 바이러스 (BFS)

  Ex)

java

열기 줄바꿈

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;

public class BFSpractice0 {

	static int MAX_COUNT = 101;
	static int [][] AdjMatrix = new int [MAX_COUNT][MAX_COUNT];
	static int[] VisitMatrix = new int[MAX_COUNT];
	static int VertaxCount, EdgeCount;
	static Queue<Integer> queue = new LinkedList<>();
	static Set<Integer> set = new HashSet<Integer>();
	
	public static void main(String[] args) {
		
		int StartV = 1;
		Scanner scan = new Scanner(System.in);
		VertaxCount = scan.nextInt();
		EdgeCount = scan.nextInt();
		for(int i = 0 ; i< EdgeCount; ++i) {
			int V1 = scan.nextInt();
			int V2 = scan.nextInt();	
			AdjMatrix[V1][V2] = 1;
			AdjMatrix[V2][V1] = 1;
		}
		BFSmethod(StartV);
		System.out.println(set.size());
	}
	
	public static void BFSmethod(int _StartVertax) {
		
		VisitMatrix[_StartVertax] = 1;
		queue.add(_StartVertax);
	 // System.out.printf("%d에서 시작\n", _StartVertax);
		
		while(false == queue.isEmpty()) {
			int currV = queue.poll();
			for(int i = 1; i <= VertaxCount ;++i) 
				if(0 == VisitMatrix[i] && 1 == AdjMatrix[currV][i]) {
					VisitMatrix[currV] = 1;
					queue.add(i);
					set.add(i);
				 // System.out.printf("%d에서 %d로 이동\n", currV, i );
				}
			}
		}
	}	
}

 

  Note) 입출력 예시

java

열기 줄바꿈

[입력]
7
6
1 2
2 3
1 5
5 2
5 6
4 7

[출력]
4