[Java] 백준 2606번: 바이러스

문제

💡 일단 생각하기!

간단히 BFS로 풀이한 문제다.
Queue에 1번 컴퓨터부터 넣어서 연결된 컴퓨터의 개수를 세준다. 이때, 1번 컴퓨터부터 탐색을 시작한다는 부분을 못 읽어서 틀렸다가 수정했다. 문제 똑바로 읽기!
일단 BFS, DFS 관련 문제들 난이도 높여가면서 풀고 구현으로 넘어가야겠다. 만만한게 BFS DFS지 🙄

풀이

package 알고리즘;

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

/**
 * 백준 2606번 바이러스
 * 메모리 : KB 시간 : ms
 * 
 * 아이디어
 * - BFS 사용
 * - 간단히 1번 컴퓨터를 시작으로 연결된 컴퓨터의 개수를 세면 되는 문제
 * - Queue에 1번부터 넣어서 연결된 컴퓨터를 queue가 빌때까지 세준다
 * - 문제를 제대로 안 읽어서 1번부터 넣어야 되는줄 모르고 틀렸다 문제 제대로 읽기!
 */

public class BJ_2606_바이러스_김유나 {
	static int arr[][], N, count = 0;
	static boolean isSelected[];
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		N = Integer.parseInt(br.readLine()); // 컴퓨터의 수 (1 <= N <= 100)
		int M = Integer.parseInt(br.readLine()); // 연결되어 있는 컴퓨터 쌍의 수
		
		arr = new int[N + 1][N + 1];
		isSelected = new boolean[N + 1];
		
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			arr[a][b] = 1;
			arr[b][a] = 1;
		}
		
		bfs(1); // 1부터 시작
		System.out.println(count);
	}
	
	static void bfs(int M) {
		Queue<Integer> q = new ArrayDeque<>();
		q.add(M);
		isSelected[M] = true;
		
		while (!q.isEmpty()) {
			int cur = q.poll();
			
			for (int i = 1; i <= N; i++) {
				// cur번 컴퓨터와 연결되어 있고 아직 count하지 않은 경우
				if (arr[cur][i] == 1 && !isSelected[i]) {
					q.add(i);
					isSelected[i] = true;
					count++;
				}
			}
		}
	}
}