[백준]2606.바이러스/Java

10246 단어 baekjoonbaekjoon

📃바이러스 링크


👩🏻‍💻풀이

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

public class virus_2606 {
	static int[][] matrix;
	static boolean[] visited;
	static int count;
	
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		int node = scan.nextInt();
		int edge = scan.nextInt();
		
		matrix = new int[node+1][node+1];
		
		for(int i = 0; i < edge; i++) {
			int x = scan.nextInt();
			int y = scan.nextInt();
			matrix[x][y] = matrix[y][x] = 1;
		}
		visited = new boolean[node+1];
		bfs(1);
	}

	private static void bfs(int start) {
		Queue<Integer> que = new LinkedList<Integer>();
		
		que.add(start);
		visited[start] = true;
		
		while(!que.isEmpty()) {
			int check = que.peek();
			que.poll();
			for(int i = 1; i < matrix.length; i++) {
				if(matrix[check][i] == 1 && visited[i] == false) {
					que.add(i);
					visited[i] = true;
					count++;
				}
			}
		}
		System.out.println(count);
	}
}


인접행렬을 만들어주고 BFS(너비우선탐색)를 사용하여 구현해보았당
큐에서 하나씩 꺼내어 검사를 진행했고, 큐에 값이 존재하지 않을 때까지 반복했다🙃

좋은 웹페이지 즐겨찾기