[자바] 백준 2606 - 바이러스

어려운 문제도 이렇게 쉽게 풀렸으면 좋겠다 하하하하하

 

ArrayList 배열을 만들어서 BFS로 풀었다.

Queue에다가 1이랑 이어진 컴퓨터들 번호 넣고, infected 여부 체크해서 infected=false인 컴퓨터들만 다시 큐에다가 집어 넣어줬다. 이미 감염 확인된 컴퓨터라면 감염을 확인한 시점에 연결된 컴퓨터들을 다 큐에다가 넣어줬을 테니까!

 

N의 범위가 작아서 인접 리스트 대신에 N+1 x N+1 행렬을 만들어서 체크했어도 됐을 것 같다.

음 예를 들어, network[A][B] = 1 = network[B]=[A] 이런 식으로?

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;

public class Main2606_바이러스 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine().trim());
		int M = Integer.parseInt(br.readLine().trim());
		
		ArrayList<Integer>[] network = new ArrayList[N+1];
		for(int n=1;n<=N;n++) {
			network[n] = new ArrayList<Integer>();
		}
		
		String[] str;
		int A,B;
		for(int m=1;m<=M;m++) {
			str = br.readLine().trim().split(" ");
			
			A = Integer.parseInt(str[0]);
			B = Integer.parseInt(str[1]);
			
			network[A].add(B);
			network[B].add(A);
		}
	
		boolean[] infected = new boolean[N+1];
		Queue<Integer> que = new LinkedList<Integer>();
		que.add(1);
		infected[1] = true;
		int cnt = 0;
		
		int now;
		while(!que.isEmpty()) {
			now = que.poll();

			ArrayList<Integer> connected = new ArrayList<Integer>();
			connected = network[now];
			for (Integer i : connected) {
				if(!infected[i]) {
					infected[i] = true;
					cnt++;
					que.add(i);
				}
			}
		}
		System.out.println(cnt);
	}
}